Clover icon

compiler

  1. Project Clover database Thu Jan 12 2023 14:04:05 MST
  2. Package com.google.javascript.jscomp

File NodeUtil.java

 

Coverage histogram

../../../../img/srcFileCovDistChart9.png
50% of files have more coverage

Code metrics

386
1,395
169
11
3,279
2,131
893
0.64
8.25
15.36
5.28

Classes

Class Line # Actions
NodeUtil 48 1,378 878 190
0.900835190.1%
NodeUtil.NumbericResultPredicate 1321 1 1 0
1.0100%
NodeUtil.BooleanResultPredicate 1374 1 1 0
1.0100%
NodeUtil.MayBeStringResultPredicate 1420 1 1 0
1.0100%
NodeUtil.VarCollector 2480 6 5 1
0.923076992.3%
NodeUtil.MatchNameNode 2587 2 2 0
1.0100%
NodeUtil.MatchNodeType 2603 2 2 0
1.0100%
NodeUtil.MatchDeclaration 2620 1 1 0
1.0100%
NodeUtil.MatchNotFunction 2630 1 1 0
1.0100%
NodeUtil.MatchShallowStatement 2642 2 1 0
1.0100%
NodeUtil.Visitor 2733 0 0 0
-1.0 -
 

Contributing tests

This file is covered by 1929 tests. .

Source view

1    /*
2    * Copyright 2004 The Closure Compiler Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10    * Unless required by applicable law or agreed to in writing, software
11    * distributed under the License is distributed on an "AS IS" BASIS,
12    * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    * See the License for the specific language governing permissions and
14    * limitations under the License.
15    */
16   
17    package com.google.javascript.jscomp;
18   
19    import com.google.common.base.Preconditions;
20    import com.google.common.base.Predicate;
21    import com.google.common.base.Predicates;
22    import com.google.common.collect.ImmutableSet;
23    import com.google.common.collect.Maps;
24    import com.google.javascript.rhino.IR;
25    import com.google.javascript.rhino.InputId;
26    import com.google.javascript.rhino.JSDocInfo;
27    import com.google.javascript.rhino.Node;
28    import com.google.javascript.rhino.Token;
29    import com.google.javascript.rhino.TokenStream;
30    import com.google.javascript.rhino.jstype.FunctionType;
31    import com.google.javascript.rhino.jstype.JSType;
32    import com.google.javascript.rhino.jstype.StaticSourceFile;
33    import com.google.javascript.rhino.jstype.TernaryValue;
34   
35    import java.util.Arrays;
36    import java.util.Collection;
37    import java.util.Collections;
38    import java.util.HashSet;
39    import java.util.Map;
40    import java.util.Set;
41   
42    import javax.annotation.Nullable;
43   
44    /**
45    * NodeUtil contains generally useful AST utilities.
46    *
47    */
 
48    public final class NodeUtil {
49   
50    static final long MAX_POSITIVE_INTEGER_NUMBER = (long) Math.pow(2, 53);
51   
52    static final String JSC_PROPERTY_NAME_FN = "JSCompiler_renameProperty";
53   
54    static final char LARGEST_BASIC_LATIN = 0x7f;
55   
56    /** the set of builtin constructors that don't have side effects. */
57    private static final Set<String> CONSTRUCTORS_WITHOUT_SIDE_EFFECTS =
58    new HashSet<String>(Arrays.asList(
59    "Array",
60    "Date",
61    "Error",
62    "Object",
63    "RegExp",
64    "XMLHttpRequest"));
65   
66    // Utility class; do not instantiate.
 
67  0 toggle private NodeUtil() {}
68   
69    /**
70    * Gets the boolean value of a node that represents a expression. This method
71    * effectively emulates the <code>Boolean()</code> JavaScript cast function.
72    * Note: unlike getBooleanValue this function does not return UNKNOWN
73    * for expressions with side-effects.
74    */
 
75  624 toggle static TernaryValue getImpureBooleanValue(Node n) {
76  624 switch (n.getType()) {
77  20 case Token.ASSIGN:
78  12 case Token.COMMA:
79    // For ASSIGN and COMMA the value is the value of the RHS.
80  32 return getImpureBooleanValue(n.getLastChild());
81  16 case Token.NOT:
82  16 TernaryValue value = getImpureBooleanValue(n.getLastChild());
83  16 return value.not();
84  12 case Token.AND: {
85  12 TernaryValue lhs = getImpureBooleanValue(n.getFirstChild());
86  12 TernaryValue rhs = getImpureBooleanValue(n.getLastChild());
87  12 return lhs.and(rhs);
88    }
89  7 case Token.OR: {
90  7 TernaryValue lhs = getImpureBooleanValue(n.getFirstChild());
91  7 TernaryValue rhs = getImpureBooleanValue(n.getLastChild());
92  7 return lhs.or(rhs);
93    }
94  6 case Token.HOOK: {
95  6 TernaryValue trueValue = getImpureBooleanValue(
96    n.getFirstChild().getNext());
97  6 TernaryValue falseValue = getImpureBooleanValue(n.getLastChild());
98  6 if (trueValue.equals(falseValue)) {
99  2 return trueValue;
100    } else {
101  4 return TernaryValue.UNKNOWN;
102    }
103    }
104  4 case Token.ARRAYLIT:
105  4 case Token.OBJECTLIT:
106    // ignoring side-effects
107  8 return TernaryValue.TRUE;
108   
109  7 case Token.VOID:
110  7 return TernaryValue.FALSE;
111   
112  536 default:
113  536 return getPureBooleanValue(n);
114    }
115    }
116   
117    /**
118    * Gets the boolean value of a node that represents a literal. This method
119    * effectively emulates the <code>Boolean()</code> JavaScript cast function
120    * except it return UNKNOWN for known values with side-effects, use
121    * getImpureBooleanValue if you don't care about side-effects.
122    */
 
123  8085 toggle static TernaryValue getPureBooleanValue(Node n) {
124  8085 switch (n.getType()) {
125  7 case Token.STRING:
126  7 return TernaryValue.forBoolean(n.getString().length() > 0);
127   
128  3814 case Token.NUMBER:
129  3814 return TernaryValue.forBoolean(n.getDouble() != 0);
130   
131  702 case Token.NOT:
132  702 return getPureBooleanValue(n.getLastChild()).not();
133   
134  3 case Token.NULL:
135  61 case Token.FALSE:
136  64 return TernaryValue.FALSE;
137   
138  8 case Token.VOID:
139  8 if (!mayHaveSideEffects(n.getFirstChild())) {
140  7 return TernaryValue.FALSE;
141    }
142  1 break;
143   
144  1817 case Token.NAME:
145  1817 String name = n.getString();
146  1817 if ("undefined".equals(name)
147    || "NaN".equals(name)) {
148    // We assume here that programs don't change the value of the keyword
149    // undefined to something other than the value undefined.
150  10 return TernaryValue.FALSE;
151  1807 } else if ("Infinity".equals(name)) {
152  1297 return TernaryValue.TRUE;
153    }
154  510 break;
155   
156  78 case Token.TRUE:
157  10 case Token.REGEXP:
158  88 return TernaryValue.TRUE;
159   
160  2 case Token.ARRAYLIT:
161  2 case Token.OBJECTLIT:
162  4 if (!mayHaveSideEffects(n)) {
163  2 return TernaryValue.TRUE;
164    }
165  2 break;
166    }
167   
168  2094 return TernaryValue.UNKNOWN;
169    }
170   
171    /**
172    * Gets the value of a node as a String, or null if it cannot be converted.
173    * When it returns a non-null String, this method effectively emulates the
174    * <code>String()</code> JavaScript cast function.
175    */
 
176  1324 toggle static String getStringValue(Node n) {
177    // TODO(user): regex literals as well.
178  1324 switch (n.getType()) {
179  1217 case Token.STRING:
180  35 case Token.STRING_KEY:
181  1252 return n.getString();
182   
183  9 case Token.NAME:
184  9 String name = n.getString();
185  9 if ("undefined".equals(name)
186    || "Infinity".equals(name)
187    || "NaN".equals(name)) {
188  6 return name;
189    }
190  3 break;
191   
192  29 case Token.NUMBER:
193  29 return getStringValue(n.getDouble());
194   
195  4 case Token.FALSE:
196  4 return "false";
197   
198  4 case Token.TRUE:
199  4 return "true";
200   
201  3 case Token.NULL:
202  3 return "null";
203   
204  2 case Token.VOID:
205  2 return "undefined";
206   
207  0 case Token.NOT:
208  0 TernaryValue child = getPureBooleanValue(n.getFirstChild());
209  0 if (child != TernaryValue.UNKNOWN) {
210  0 return child.toBoolean(true) ? "false" : "true"; // reversed.
211    }
212  0 break;
213   
214  19 case Token.ARRAYLIT:
215  19 return arrayToString(n);
216   
217  1 case Token.OBJECTLIT:
218  1 return "[object Object]";
219    }
220  4 return null;
221    }
222   
 
223  29 toggle static String getStringValue(double value) {
224  29 long longValue = (long) value;
225   
226    // Return "1" instead of "1.0"
227  29 if (longValue == value) {
228  29 return Long.toString(longValue);
229    } else {
230  0 return Double.toString(value);
231    }
232    }
233   
234    /**
235    * When converting arrays to string using Array.prototype.toString or
236    * Array.prototype.join, the rules for conversion to String are different
237    * than converting each element individually. Specifically, "null" and
238    * "undefined" are converted to an empty string.
239    * @param n A node that is a member of an Array.
240    * @return The string representation.
241    */
 
242  128 toggle static String getArrayElementStringValue(Node n) {
243  128 return (NodeUtil.isNullOrUndefined(n) || n.isEmpty())
244    ? "" : getStringValue(n);
245    }
246   
 
247  19 toggle static String arrayToString(Node literal) {
248  19 Node first = literal.getFirstChild();
249  19 StringBuilder result = new StringBuilder();
250  19 int nextSlot = 0;
251  19 int nextSkipSlot = 0;
252  38 for (Node n = first; n != null; n = n.getNext()) {
253  21 String childValue = getArrayElementStringValue(n);
254  21 if (childValue == null) {
255  2 return null;
256    }
257  19 if (n != first) {
258  4 result.append(',');
259    }
260  19 result.append(childValue);
261   
262  19 nextSlot++;
263    }
264  17 return result.toString();
265    }
266   
267    /**
268    * Gets the value of a node as a Number, or null if it cannot be converted.
269    * When it returns a non-null Double, this method effectively emulates the
270    * <code>Number()</code> JavaScript cast function.
271    */
 
272  9128 toggle static Double getNumberValue(Node n) {
273  9128 switch (n.getType()) {
274  446 case Token.TRUE:
275  446 return 1.0;
276   
277  444 case Token.FALSE:
278  387 case Token.NULL:
279  831 return 0.0;
280   
281  2986 case Token.NUMBER:
282  2986 return n.getDouble();
283   
284  275 case Token.VOID:
285  275 if (mayHaveSideEffects(n.getFirstChild())) {
286  1 return null;
287    } else {
288  274 return Double.NaN;
289    }
290   
291  2119 case Token.NAME:
292    // Check for known constants
293  2119 String name = n.getString();
294  2119 if (name.equals("undefined")) {
295  273 return Double.NaN;
296    }
297  1846 if (name.equals("NaN")) {
298  1376 return Double.NaN;
299    }
300  470 if (name.equals("Infinity")) {
301  282 return Double.POSITIVE_INFINITY;
302    }
303  188 return null;
304   
305  550 case Token.NEG:
306  550 if (n.getChildCount() == 1 && n.getFirstChild().isName()
307    && n.getFirstChild().getString().equals("Infinity")) {
308  549 return Double.NEGATIVE_INFINITY;
309    }
310  1 return null;
311   
312  544 case Token.NOT:
313  544 TernaryValue child = getPureBooleanValue(n.getFirstChild());
314  544 if (child != TernaryValue.UNKNOWN) {
315  544 return child.toBoolean(true) ? 0.0 : 1.0; // reversed.
316    }
317  0 break;
318   
319  1133 case Token.STRING:
320  1133 return getStringNumberValue(n.getString());
321   
322  0 case Token.ARRAYLIT:
323  0 case Token.OBJECTLIT:
324  0 String value = getStringValue(n);
325  0 return value != null ? getStringNumberValue(value) : null;
326    }
327   
328  244 return null;
329    }
330   
 
331  1178 toggle static Double getStringNumberValue(String rawJsString) {
332  1178 if (rawJsString.contains("\u000b")) {
333    // vertical tab is not always whitespace
334  2 return null;
335    }
336   
337  1176 String s = trimJsWhiteSpace(rawJsString);
338    // return ScriptRuntime.toNumber(s);
339  1176 if (s.length() == 0) {
340  277 return 0.0;
341    }
342   
343  899 if (s.length() > 2
344    && s.charAt(0) == '0'
345    && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) {
346    // Attempt to convert hex numbers.
347  9 try {
348  9 return Double.valueOf(Integer.parseInt(s.substring(2), 16));
349    } catch (NumberFormatException e) {
350  1 return Double.NaN;
351    }
352    }
353   
354  890 if (s.length() > 3
355    && (s.charAt(0) == '-' || s.charAt(0) == '+')
356    && s.charAt(1) == '0'
357    && (s.charAt(2) == 'x' || s.charAt(2) == 'X')) {
358    // hex numbers with explicit signs vary between browsers.
359  6 return null;
360    }
361   
362    // Firefox and IE treat the "Infinity" differently. Firefox is case
363    // insensitive, but IE treats "infinity" as NaN. So leave it alone.
364  884 if (s.equals("infinity")
365    || s.equals("-infinity")
366    || s.equals("+infinity")) {
367  3 return null;
368    }
369   
370  881 try {
371  881 return Double.parseDouble(s);
372    } catch (NumberFormatException e) {
373  555 return Double.NaN;
374    }
375    }
376   
 
377  1219 toggle static String trimJsWhiteSpace(String s) {
378  1219 int start = 0;
379  1219 int end = s.length();
380  1224 while (end > 0
381    && isStrWhiteSpaceChar(s.charAt(end - 1)) == TernaryValue.TRUE) {
382  5 end--;
383    }
384  1230 while (start < end
385    && isStrWhiteSpaceChar(s.charAt(start)) == TernaryValue.TRUE) {
386  11 start++;
387    }
388  1219 return s.substring(start, end);
389    }
390   
391    /**
392    * Copied from Rhino's ScriptRuntime
393    */
 
394  1896 toggle public static TernaryValue isStrWhiteSpaceChar(int c) {
395  1896 switch (c) {
396  0 case '\u000B': // <VT>
397  0 return TernaryValue.UNKNOWN; // IE says "no", ECMAScript says "yes"
398  14 case ' ': // <SP>
399  0 case '\n': // <LF>
400  0 case '\r': // <CR>
401  1 case '\t': // <TAB>
402  0 case '\u00A0': // <NBSP>
403  0 case '\u000C': // <FF>
404  0 case '\u2028': // <LS>
405  0 case '\u2029': // <PS>
406  1 case '\uFEFF': // <BOM>
407  16 return TernaryValue.TRUE;
408  1880 default:
409  1880 return (Character.getType(c) == Character.SPACE_SEPARATOR)
410    ? TernaryValue.TRUE : TernaryValue.FALSE;
411    }
412    }
413   
414    /**
415    * Gets the function's name. This method recognizes five forms:
416    * <ul>
417    * <li>{@code function name() ...}</li>
418    * <li>{@code var name = function() ...}</li>
419    * <li>{@code qualified.name = function() ...}</li>
420    * <li>{@code var name2 = function name1() ...}</li>
421    * <li>{@code qualified.name2 = function name1() ...}</li>
422    * </ul>
423    * In two last cases with named function expressions, the second name is
424    * returned (the variable of qualified name).
425    *
426    * @param n a node whose type is {@link Token#FUNCTION}
427    * @return the function's name, or {@code null} if it has no name
428    */
 
429  623 toggle static String getFunctionName(Node n) {
430  623 Preconditions.checkState(n.isFunction());
431  623 Node parent = n.getParent();
432  623 switch (parent.getType()) {
433  84 case Token.NAME:
434    // var name = function() ...
435    // var name2 = function name1() ...
436  84 return parent.getQualifiedName();
437   
438  95 case Token.ASSIGN:
439    // qualified.name = function() ...
440    // qualified.name2 = function name1() ...
441  95 return parent.getFirstChild().getQualifiedName();
442   
443  444 default:
444    // function name() ...
445  444 String name = n.getFirstChild().getQualifiedName();
446  444 return name;
447    }
448    }
449   
450    /**
451    * Gets the function's name. This method recognizes the forms:
452    * <ul>
453    * <li>{@code &#123;'name': function() ...&#125;}</li>
454    * <li>{@code &#123;name: function() ...&#125;}</li>
455    * <li>{@code function name() ...}</li>
456    * <li>{@code var name = function() ...}</li>
457    * <li>{@code qualified.name = function() ...}</li>
458    * <li>{@code var name2 = function name1() ...}</li>
459    * <li>{@code qualified.name2 = function name1() ...}</li>
460    * </ul>
461    *
462    * @param n a node whose type is {@link Token#FUNCTION}
463    * @return the function's name, or {@code null} if it has no name
464    */
 
465  18 toggle public static String getNearestFunctionName(Node n) {
466  18 if (!n.isFunction()) {
467  0 return null;
468    }
469   
470  18 String name = getFunctionName(n);
471  18 if (name != null) {
472  11 return name;
473    }
474   
475    // Check for the form { 'x' : function() { } }
476  7 Node parent = n.getParent();
477  7 switch (parent.getType()) {
478  2 case Token.SETTER_DEF:
479  1 case Token.GETTER_DEF:
480  3 case Token.STRING_KEY:
481    // Return the name of the literal's key.
482  6 return parent.getString();
483  0 case Token.NUMBER:
484  0 return getStringValue(parent);
485    }
486   
487  1 return null;
488    }
489   
490   
491    /**
492    * Returns true if this is an immutable value.
493    */
 
494  27301 toggle static boolean isImmutableValue(Node n) {
495  27301 switch (n.getType()) {
496  4460 case Token.STRING:
497  4585 case Token.NUMBER:
498  1094 case Token.NULL:
499  1900 case Token.TRUE:
500  1878 case Token.FALSE:
501  13917 return true;
502  0 case Token.CAST:
503  768 case Token.NOT:
504  768 return isImmutableValue(n.getFirstChild());
505  842 case Token.VOID:
506  1076 case Token.NEG:
507  1918 return isImmutableValue(n.getFirstChild());
508  5577 case Token.NAME:
509  5577 String name = n.getString();
510    // We assume here that programs don't change the value of the keyword
511    // undefined to something other than the value undefined.
512  5577 return "undefined".equals(name)
513    || "Infinity".equals(name)
514    || "NaN".equals(name);
515    }
516   
517  5121 return false;
518    }
519   
520    /**
521    * Returns true if the operator on this node is symmetric
522    */
 
523  4168 toggle static boolean isSymmetricOperation(Node n) {
524  4168 switch (n.getType()) {
525  54 case Token.EQ: // equal
526  54 case Token.NE: // not equal
527  56 case Token.SHEQ: // exactly equal
528  54 case Token.SHNE: // exactly not equal
529  54 case Token.MUL: // multiply, unlike add it only works on numbers
530    // or results NaN if any of the operators is not a number
531  272 return true;
532    }
533  3896 return false;
534    }
535   
536    /**
537    * Returns true if the operator on this node is relational.
538    * the returned set does not include the equalities.
539    */
 
540  3997 toggle static boolean isRelationalOperation(Node n) {
541  3997 switch (n.getType()) {
542  54 case Token.GT: // equal
543  54 case Token.GE: // not equal
544  54 case Token.LT: // exactly equal
545  54 case Token.LE: // exactly not equal
546  216 return true;
547    }
548  3781 return false;
549    }
550   
551    /**
552    * Returns the inverse of an operator if it is invertible.
553    * ex. '>' ==> '<'
554    */
 
555  40 toggle static int getInverseOperator(int type) {
556  40 switch (type) {
557  10 case Token.GT:
558  10 return Token.LT;
559  10 case Token.LT:
560  10 return Token.GT;
561  10 case Token.GE:
562  10 return Token.LE;
563  10 case Token.LE:
564  10 return Token.GE;
565    }
566  0 return Token.ERROR;
567    }
568   
569    /**
570    * Returns true if this is a literal value. We define a literal value
571    * as any node that evaluates to the same thing regardless of when or
572    * where it is evaluated. So /xyz/ and [3, 5] are literals, but
573    * the name a is not.
574    *
575    * Function literals do not meet this definition, because they
576    * lexically capture variables. For example, if you have
577    * <code>
578    * function() { return a; }
579    * </code>
580    * If it is evaluated in a different scope, then it
581    * captures a different variable. Even if the function did not read
582    * any captured variables directly, it would still fail this definition,
583    * because it affects the lifecycle of variables in the enclosing scope.
584    *
585    * However, a function literal with respect to a particular scope is
586    * a literal.
587    *
588    * @param includeFunctions If true, all function expressions will be
589    * treated as literals.
590    */
 
591  18238 toggle static boolean isLiteralValue(Node n, boolean includeFunctions) {
592  18238 switch (n.getType()) {
593  0 case Token.CAST:
594  0 return isLiteralValue(n.getFirstChild(), includeFunctions);
595   
596  43 case Token.ARRAYLIT:
597  71 for (Node child = n.getFirstChild(); child != null;
598    child = child.getNext()) {
599  39 if ((!child.isEmpty()) && !isLiteralValue(child, includeFunctions)) {
600  11 return false;
601    }
602    }
603  32 return true;
604   
605  14 case Token.REGEXP:
606    // Return true only if all children are const.
607  40 for (Node child = n.getFirstChild(); child != null;
608    child = child.getNext()) {
609  26 if (!isLiteralValue(child, includeFunctions)) {
610  0 return false;
611    }
612    }
613  14 return true;
614   
615  33 case Token.OBJECTLIT:
616    // Return true only if all values are const.
617  39 for (Node child = n.getFirstChild(); child != null;
618    child = child.getNext()) {
619  16 if (!isLiteralValue(child.getFirstChild(), includeFunctions)) {
620  10 return false;
621    }
622    }
623  23 return true;
624   
625  54 case Token.FUNCTION:
626  54 return includeFunctions && !NodeUtil.isFunctionDeclaration(n);
627   
628  18094 default:
629  18094 return isImmutableValue(n);
630    }
631    }
632   
633    /**
634    * Determines whether the given value may be assigned to a define.
635    *
636    * @param val The value being assigned.
637    * @param defines The list of names of existing defines.
638    */
 
639  64 toggle static boolean isValidDefineValue(Node val, Set<String> defines) {
640  64 switch (val.getType()) {
641  5 case Token.STRING:
642  8 case Token.NUMBER:
643  12 case Token.TRUE:
644  22 case Token.FALSE:
645  47 return true;
646   
647    // Binary operators are only valid if both children are valid.
648  3 case Token.ADD:
649  2 case Token.BITAND:
650  0 case Token.BITNOT:
651  0 case Token.BITOR:
652  0 case Token.BITXOR:
653  0 case Token.DIV:
654  0 case Token.EQ:
655  0 case Token.GE:
656  0 case Token.GT:
657  0 case Token.LE:
658  0 case Token.LSH:
659  0 case Token.LT:
660  0 case Token.MOD:
661  0 case Token.MUL:
662  0 case Token.NE:
663  0 case Token.RSH:
664  0 case Token.SHEQ:
665  0 case Token.SHNE:
666  0 case Token.SUB:
667  0 case Token.URSH:
668  5 return isValidDefineValue(val.getFirstChild(), defines)
669    && isValidDefineValue(val.getLastChild(), defines);
670   
671    // Unary operators are valid if the child is valid.
672  3 case Token.NOT:
673  1 case Token.NEG:
674  0 case Token.POS:
675  4 return isValidDefineValue(val.getFirstChild(), defines);
676   
677    // Names are valid if and only if they are defines themselves.
678  6 case Token.NAME:
679  1 case Token.GETPROP:
680  7 if (val.isQualifiedName()) {
681  7 return defines.contains(val.getQualifiedName());
682    }
683    }
684  1 return false;
685    }
686   
687    /**
688    * Returns whether this a BLOCK node with no children.
689    *
690    * @param block The node.
691    */
 
692  64 toggle static boolean isEmptyBlock(Node block) {
693  64 if (!block.isBlock()) {
694  0 return false;
695    }
696   
697  64 for (Node n = block.getFirstChild(); n != null; n = n.getNext()) {
698  45 if (!n.isEmpty()) {
699  45 return false;
700    }
701    }
702  19 return true;
703    }
704   
 
705  7148 toggle static boolean isSimpleOperator(Node n) {
706  7148 return isSimpleOperatorType(n.getType());
707    }
708   
709    /**
710    * A "simple" operator is one whose children are expressions,
711    * has no direct side-effects (unlike '+='), and has no
712    * conditional aspects (unlike '||').
713    */
 
714  7148 toggle static boolean isSimpleOperatorType(int type) {
715  7148 switch (type) {
716  92 case Token.ADD:
717  0 case Token.BITAND:
718  1 case Token.BITNOT:
719  0 case Token.BITOR:
720  0 case Token.BITXOR:
721  54 case Token.COMMA:
722  2 case Token.DIV:
723  2 case Token.EQ:
724  4 case Token.GE:
725  125 case Token.GETELEM:
726  1089 case Token.GETPROP:
727  1 case Token.GT:
728  1 case Token.INSTANCEOF:
729  0 case Token.LE:
730  0 case Token.LSH:
731  0 case Token.LT:
732  0 case Token.MOD:
733  1 case Token.MUL:
734  1 case Token.NE:
735  24 case Token.NOT:
736  0 case Token.RSH:
737  1 case Token.SHEQ:
738  0 case Token.SHNE:
739  4 case Token.SUB:
740  1 case Token.TYPEOF:
741  149 case Token.VOID:
742  2 case Token.POS:
743  1 case Token.NEG:
744  0 case Token.URSH:
745  1556 return true;
746   
747  5592 default:
748  5592 return false;
749    }
750    }
751   
752    /**
753    * Creates an EXPR_RESULT.
754    *
755    * @param child The expression itself.
756    * @return Newly created EXPR node with the child as subexpression.
757    */
 
758  177 toggle static Node newExpr(Node child) {
759  177 return IR.exprResult(child).srcref(child);
760    }
761   
762    /**
763    * Returns true if the node may create new mutable state, or change existing
764    * state.
765    *
766    * @see <a href="http://www.xkcd.org/326/">XKCD Cartoon</a>
767    */
 
768  159 toggle static boolean mayEffectMutableState(Node n) {
769  159 return mayEffectMutableState(n, null);
770    }
771   
 
772  186 toggle static boolean mayEffectMutableState(Node n, AbstractCompiler compiler) {
773  186 return checkForStateChangeHelper(n, true, compiler);
774    }
775   
776    /**
777    * Returns true if the node which may have side effects when executed.
778    */
 
779  676 toggle static boolean mayHaveSideEffects(Node n) {
780  676 return mayHaveSideEffects(n, null);
781    }
782   
 
783  5044 toggle static boolean mayHaveSideEffects(Node n, AbstractCompiler compiler) {
784  5044 return checkForStateChangeHelper(n, false, compiler);
785    }
786   
787    /**
788    * Returns true if some node in n's subtree changes application state.
789    * If {@code checkForNewObjects} is true, we assume that newly created
790    * mutable objects (like object literals) change state. Otherwise, we assume
791    * that they have no side effects.
792    */
 
793  10327 toggle private static boolean checkForStateChangeHelper(
794    Node n, boolean checkForNewObjects, AbstractCompiler compiler) {
795    // Rather than id which ops may have side effects, id the ones
796    // that we know to be safe
797  10327 switch (n.getType()) {
798    // other side-effect free statements and expressions
799  0 case Token.CAST:
800  48 case Token.AND:
801  461 case Token.BLOCK:
802  1632 case Token.EXPR_RESULT:
803  43 case Token.HOOK:
804  91 case Token.IF:
805  7 case Token.IN:
806  0 case Token.PARAM_LIST:
807  967 case Token.NUMBER:
808  45 case Token.OR:
809  96 case Token.THIS:
810  35 case Token.TRUE:
811  24 case Token.FALSE:
812  6 case Token.NULL:
813  726 case Token.STRING:
814  0 case Token.STRING_KEY:
815  43 case Token.SWITCH:
816  45 case Token.TRY:
817  13 case Token.EMPTY:
818  4282 break;
819   
820    // Throws are by definition side effects
821  25 case Token.THROW:
822  25 return true;
823   
824  87 case Token.OBJECTLIT:
825  87 if (checkForNewObjects) {
826  2 return true;
827    }
828  128 for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
829  48 if (checkForStateChangeHelper(
830    c.getFirstChild(), checkForNewObjects, compiler)) {
831  5 return true;
832    }
833    }
834  80 return false;
835   
836  43 case Token.ARRAYLIT:
837  15 case Token.REGEXP:
838  58 if (checkForNewObjects) {
839  6 return true;
840    }
841  52 break;
842   
843  544 case Token.VAR: // empty var statement (no declaration)
844  885 case Token.NAME: // variable by itself
845  1429 if (n.getFirstChild() != null) {
846  544 return true;
847    }
848  885 break;
849   
850  394 case Token.FUNCTION:
851    // Function expressions don't have side-effects, but function
852    // declarations change the namespace. Either way, we don't need to
853    // check the children, since they aren't executed at declaration time.
854  394 return checkForNewObjects || !isFunctionExpression(n);
855   
856  89 case Token.NEW:
857  89 if (checkForNewObjects) {
858  12 return true;
859    }
860   
861  77 if (!constructorCallHasSideEffects(n)) {
862    // loop below will see if the constructor parameters have
863    // side-effects
864  18 break;
865    }
866  59 return true;
867   
868  1297 case Token.CALL:
869    // calls to functions that have no side effects have the no
870    // side effect property set.
871  1297 if (!functionCallHasSideEffects(n, compiler)) {
872    // loop below will see if the function parameters have
873    // side-effects
874  18 break;
875    }
876  1279 return true;
877   
878  2666 default:
879  2666 if (isSimpleOperator(n)) {
880  937 break;
881    }
882   
883  1729 if (isAssignmentOp(n)) {
884  905 Node assignTarget = n.getFirstChild();
885  905 if (assignTarget.isName()) {
886  514 return true;
887    }
888   
889    // Assignments will have side effects if
890    // a) The RHS has side effects, or
891    // b) The LHS has side effects, or
892    // c) A name on the LHS will exist beyond the life of this statement.
893  391 if (checkForStateChangeHelper(
894    n.getFirstChild(), checkForNewObjects, compiler) ||
895    checkForStateChangeHelper(
896    n.getLastChild(), checkForNewObjects, compiler)) {
897  24 return true;
898    }
899   
900  367 if (isGet(assignTarget)) {
901    // If the object being assigned to is a local object, don't
902    // consider this a side-effect as it can't be referenced
903    // elsewhere. Don't do this recursively as the property might
904    // be an alias of another object, unlike a literal below.
905  367 Node current = assignTarget.getFirstChild();
906  367 if (evaluatesToLocalValue(current)) {
907  6 return false;
908    }
909   
910    // A literal value as defined by "isLiteralValue" is guaranteed
911    // not to be an alias, or any components which are aliases of
912    // other objects.
913    // If the root object is a literal don't consider this a
914    // side-effect.
915  515 while (isGet(current)) {
916  154 current = current.getFirstChild();
917    }
918   
919  361 return !isLiteralValue(current, true);
920    } else {
921    // TODO(johnlenz): remove this code and make this an exception. This
922    // is here only for legacy reasons, the AST is not valid but
923    // preserve existing behavior.
924  0 return !isLiteralValue(assignTarget, true);
925    }
926    }
927   
928  824 return true;
929    }
930   
931  8127 for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
932  4268 if (checkForStateChangeHelper(c, checkForNewObjects, compiler)) {
933  2333 return true;
934    }
935    }
936   
937  3859 return false;
938    }
939   
940    /**
941    * Do calls to this constructor have side effects?
942    *
943    * @param callNode - constructor call node
944    */
 
945  136 toggle static boolean constructorCallHasSideEffects(Node callNode) {
946  136 return constructorCallHasSideEffects(callNode, null);
947    }
948   
 
949  176 toggle static boolean constructorCallHasSideEffects(
950    Node callNode, AbstractCompiler compiler) {
951  176 if (!callNode.isNew()) {
952  0 throw new IllegalStateException(
953    "Expected NEW node, got " + Token.name(callNode.getType()));
954    }
955   
956  176 if (callNode.isNoSideEffectsCall()) {
957  23 return false;
958    }
959   
960  153 Node nameNode = callNode.getFirstChild();
961  153 if (nameNode.isName() &&
962    CONSTRUCTORS_WITHOUT_SIDE_EFFECTS.contains(nameNode.getString())) {
963  6 return false;
964    }
965   
966  147 return true;
967    }
968   
969    // A list of built-in object creation or primitive type cast functions that
970    // can also be called as constructors but lack side-effects.
971    // TODO(johnlenz): consider adding an extern annotation for this.
972    private static final Set<String> BUILTIN_FUNCTIONS_WITHOUT_SIDEEFFECTS =
973    ImmutableSet.of(
974    "Object", "Array", "String", "Number", "Boolean", "RegExp", "Error");
975    private static final Set<String> OBJECT_METHODS_WITHOUT_SIDEEFFECTS =
976    ImmutableSet.of("toString", "valueOf");
977    private static final Set<String> REGEXP_METHODS =
978    ImmutableSet.of("test", "exec");
979    private static final Set<String> STRING_REGEXP_METHODS =
980    ImmutableSet.of("match", "replace", "search", "split");
981   
982    /**
983    * Returns true if calls to this function have side effects.
984    *
985    * @param callNode - function call node
986    */
 
987  165 toggle static boolean functionCallHasSideEffects(Node callNode) {
988  165 return functionCallHasSideEffects(callNode, null);
989    }
990   
991    /**
992    * Returns true if calls to this function have side effects.
993    *
994    * @param callNode The call node to inspected.
995    * @param compiler A compiler object to provide program state changing
996    * context information. Can be null.
997    */
 
998  2841 toggle static boolean functionCallHasSideEffects(
999    Node callNode, @Nullable AbstractCompiler compiler) {
1000  2841 if (!callNode.isCall()) {
1001  0 throw new IllegalStateException(
1002    "Expected CALL node, got " + Token.name(callNode.getType()));
1003    }
1004   
1005  2841 if (callNode.isNoSideEffectsCall()) {
1006  35 return false;
1007    }
1008   
1009  2806 Node nameNode = callNode.getFirstChild();
1010   
1011    // Built-in functions with no side effects.
1012  2806 if (nameNode.isName()) {
1013  2326 String name = nameNode.getString();
1014  2326 if (BUILTIN_FUNCTIONS_WITHOUT_SIDEEFFECTS.contains(name)) {
1015  4 return false;
1016    }
1017  480 } else if (nameNode.isGetProp()) {
1018  418 if (callNode.hasOneChild()
1019    && OBJECT_METHODS_WITHOUT_SIDEEFFECTS.contains(
1020    nameNode.getLastChild().getString())) {
1021  2 return false;
1022    }
1023   
1024  416 if (callNode.isOnlyModifiesThisCall()
1025    && evaluatesToLocalValue(nameNode.getFirstChild())) {
1026  5 return false;
1027    }
1028   
1029    // Math.floor has no side-effects.
1030    // TODO(nicksantos): This is a terrible terrible hack, until
1031    // I create a definitionProvider that understands namespacing.
1032  411 if (nameNode.getFirstChild().isName()) {
1033  239 if ("Math.floor".equals(nameNode.getQualifiedName())) {
1034  0 return false;
1035    }
1036    }
1037   
1038  411 if (compiler != null && !compiler.hasRegExpGlobalReferences()) {
1039  118 if (nameNode.getFirstChild().isRegExp()
1040    && REGEXP_METHODS.contains(nameNode.getLastChild().getString())) {
1041  6 return false;
1042  112 } else if (nameNode.getFirstChild().isString()
1043    && STRING_REGEXP_METHODS.contains(
1044    nameNode.getLastChild().getString())) {
1045  6 Node param = nameNode.getNext();
1046  6 if (param != null &&
1047    (param.isString() || param.isRegExp())) {
1048  5 return false;
1049    }
1050    }
1051    }
1052    }
1053   
1054  2784 return true;
1055    }
1056   
1057    /**
1058    * @return Whether the call has a local result.
1059    */
 
1060  56 toggle static boolean callHasLocalResult(Node n) {
1061  56 Preconditions.checkState(n.isCall());
1062  56 return (n.getSideEffectFlags() & Node.FLAG_LOCAL_RESULTS) > 0;
1063    }
1064   
1065    /**
1066    * @return Whether the new has a local result.
1067    */
 
1068  30 toggle static boolean newHasLocalResult(Node n) {
1069  30 Preconditions.checkState(n.isNew());
1070  30 return n.isOnlyModifiesThisCall();
1071    }
1072   
1073    /**
1074    * Returns true if the current node's type implies side effects.
1075    *
1076    * This is a non-recursive version of the may have side effects
1077    * check; used to check wherever the current node's type is one of
1078    * the reason's why a subtree has side effects.
1079    */
 
1080  4238 toggle static boolean nodeTypeMayHaveSideEffects(Node n) {
1081  4238 return nodeTypeMayHaveSideEffects(n, null);
1082    }
1083   
 
1084  6064 toggle static boolean nodeTypeMayHaveSideEffects(Node n, AbstractCompiler compiler) {
1085  6064 if (isAssignmentOp(n)) {
1086  606 return true;
1087    }
1088   
1089  5458 switch(n.getType()) {
1090  7 case Token.DELPROP:
1091  9 case Token.DEC:
1092  38 case Token.INC:
1093  5 case Token.THROW:
1094  59 return true;
1095  1039 case Token.CALL:
1096  1039 return NodeUtil.functionCallHasSideEffects(n, compiler);
1097  40 case Token.NEW:
1098  40 return NodeUtil.constructorCallHasSideEffects(n, compiler);
1099  1064 case Token.NAME:
1100    // A variable definition.
1101  1064 return n.hasChildren();
1102  3256 default:
1103  3256 return false;
1104    }
1105    }
1106   
1107    /**
1108    * @return Whether the tree can be affected by side-effects or
1109    * has side-effects.
1110    */
 
1111  316 toggle static boolean canBeSideEffected(Node n) {
1112  316 Set<String> emptySet = Collections.emptySet();
1113  316 return canBeSideEffected(n, emptySet);
1114    }
1115   
1116    /**
1117    * @param knownConstants A set of names known to be constant value at
1118    * node 'n' (such as locals that are last written before n can execute).
1119    * @return Whether the tree can be affected by side-effects or
1120    * has side-effects.
1121    */
 
1122  479 toggle static boolean canBeSideEffected(Node n, Set<String> knownConstants) {
1123  479 switch (n.getType()) {
1124  56 case Token.CALL:
1125  5 case Token.NEW:
1126    // Function calls or constructor can reference changed values.
1127    // TODO(johnlenz): Add some mechanism for determining that functions
1128    // are unaffected by side effects.
1129  61 return true;
1130  70 case Token.NAME:
1131    // Non-constant names values may have been changed.
1132  70 return !isConstantName(n)
1133    && !knownConstants.contains(n.getString());
1134   
1135    // Properties on constant NAMEs can still be side-effected.
1136  14 case Token.GETPROP:
1137  5 case Token.GETELEM:
1138  19 return true;
1139   
1140  5 case Token.FUNCTION:
1141    // Function expression are not changed by side-effects,
1142    // and function declarations are not part of expressions.
1143  5 Preconditions.checkState(isFunctionExpression(n));
1144  5 return false;
1145    }
1146   
1147  409 for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
1148  99 if (canBeSideEffected(c, knownConstants)) {
1149  14 return true;
1150    }
1151    }
1152   
1153  310 return false;
1154    }
1155   
1156    /*
1157    * 0 comma ,
1158    * 1 assignment = += -= *= /= %= <<= >>= >>>= &= ^= |=
1159    * 2 conditional ?:
1160    * 3 logical-or ||
1161    * 4 logical-and &&
1162    * 5 bitwise-or |
1163    * 6 bitwise-xor ^
1164    * 7 bitwise-and &
1165    * 8 equality == !=
1166    * 9 relational < <= > >=
1167    * 10 bitwise shift << >> >>>
1168    * 11 addition/subtraction + -
1169    * 12 multiply/divide * / %
1170    * 13 negation/increment ! ~ - ++ --
1171    * 14 call, member () [] .
1172    */
 
1173  223966 toggle static int precedence(int type) {
1174  223966 switch (type) {
1175  84 case Token.COMMA: return 0;
1176  103 case Token.ASSIGN_BITOR:
1177  0 case Token.ASSIGN_BITXOR:
1178  0 case Token.ASSIGN_BITAND:
1179  0 case Token.ASSIGN_LSH:
1180  0 case Token.ASSIGN_RSH:
1181  0 case Token.ASSIGN_URSH:
1182  163 case Token.ASSIGN_ADD:
1183  51 case Token.ASSIGN_SUB:
1184  33 case Token.ASSIGN_MUL:
1185  6 case Token.ASSIGN_DIV:
1186  4 case Token.ASSIGN_MOD:
1187  14403 case Token.ASSIGN: return 1;
1188  781 case Token.HOOK: return 2; // ?: operator
1189  670 case Token.OR: return 3;
1190  1378 case Token.AND: return 4;
1191  217 case Token.BITOR: return 5;
1192  190 case Token.BITXOR: return 6;
1193  190 case Token.BITAND: return 7;
1194  1586 case Token.EQ:
1195  1240 case Token.NE:
1196  1329 case Token.SHEQ:
1197  5350 case Token.SHNE: return 8;
1198  930 case Token.LT:
1199  683 case Token.GT:
1200  432 case Token.LE:
1201  438 case Token.GE:
1202  213 case Token.INSTANCEOF:
1203  2765 case Token.IN: return 9;
1204  26 case Token.LSH:
1205  17 case Token.RSH:
1206  57 case Token.URSH: return 10;
1207  313 case Token.SUB:
1208  2340 case Token.ADD: return 11;
1209  437 case Token.MUL:
1210  14 case Token.MOD:
1211  574 case Token.DIV: return 12;
1212  1068 case Token.INC:
1213  67 case Token.DEC:
1214  3133 case Token.NEW:
1215  2 case Token.DELPROP:
1216  392 case Token.TYPEOF:
1217  1062 case Token.VOID:
1218  3723 case Token.NOT:
1219  39 case Token.BITNOT:
1220  46 case Token.POS:
1221  11934 case Token.NEG: return 13;
1222   
1223  16137 case Token.CALL:
1224  3384 case Token.GETELEM:
1225  54535 case Token.GETPROP:
1226    // Data values
1227  1017 case Token.ARRAYLIT:
1228  657 case Token.EMPTY: // TODO(johnlenz): remove this.
1229  1817 case Token.FALSE:
1230  6209 case Token.FUNCTION:
1231  60448 case Token.NAME:
1232  757 case Token.NULL:
1233  23090 case Token.NUMBER:
1234  2345 case Token.OBJECTLIT:
1235  334 case Token.REGEXP:
1236  7880 case Token.STRING:
1237  240 case Token.STRING_KEY:
1238  2559 case Token.THIS:
1239  1612 case Token.TRUE:
1240  183021 return 15;
1241  12 case Token.CAST:
1242  12 return 16;
1243   
1244  0 default: throw new Error("Unknown precedence for " +
1245    Token.name(type) +
1246    " (type " + type + ")");
1247    }
1248    }
1249   
 
1250  13302 toggle static boolean isUndefined(Node n) {
1251  13302 switch (n.getType()) {
1252  454 case Token.VOID:
1253  454 return true;
1254  4990 case Token.NAME:
1255  4990 return n.getString().equals("undefined");
1256    }
1257  7858 return false;
1258    }
1259   
 
1260  145 toggle static boolean isNullOrUndefined(Node n) {
1261  145 return n.isNull() || isUndefined(n);
1262    }
1263   
1264    static final Predicate<Node> IMMUTABLE_PREDICATE = new Predicate<Node>() {
 
1265  84 toggle @Override
1266    public boolean apply(Node n) {
1267  84 return isImmutableValue(n);
1268    }
1269    };
1270   
 
1271  84 toggle static boolean isImmutableResult(Node n) {
1272  84 return allResultsMatch(n, IMMUTABLE_PREDICATE);
1273    }
1274   
1275    /**
1276    * Apply the supplied predicate against
1277    * all possible result Nodes of the expression.
1278    */
 
1279  1641 toggle static boolean allResultsMatch(Node n, Predicate<Node> p) {
1280  1641 switch (n.getType()) {
1281  0 case Token.CAST:
1282  0 return allResultsMatch(n.getFirstChild(), p);
1283  8 case Token.ASSIGN:
1284  1 case Token.COMMA:
1285  9 return allResultsMatch(n.getLastChild(), p);
1286  1 case Token.AND:
1287  3 case Token.OR:
1288  4 return allResultsMatch(n.getFirstChild(), p)
1289    && allResultsMatch(n.getLastChild(), p);
1290  3 case Token.HOOK:
1291  3 return allResultsMatch(n.getFirstChild().getNext(), p)
1292    && allResultsMatch(n.getLastChild(), p);
1293  1625 default:
1294  1625 return p.apply(n);
1295    }
1296    }
1297   
1298    /**
1299    * Apply the supplied predicate against
1300    * all possible result Nodes of the expression.
1301    */
 
1302  924 toggle static boolean anyResultsMatch(Node n, Predicate<Node> p) {
1303  924 switch (n.getType()) {
1304  0 case Token.CAST:
1305  0 return anyResultsMatch(n.getFirstChild(), p);
1306  1 case Token.ASSIGN:
1307  1 case Token.COMMA:
1308  2 return anyResultsMatch(n.getLastChild(), p);
1309  1 case Token.AND:
1310  9 case Token.OR:
1311  10 return anyResultsMatch(n.getFirstChild(), p)
1312    || anyResultsMatch(n.getLastChild(), p);
1313  25 case Token.HOOK:
1314  25 return anyResultsMatch(n.getFirstChild().getNext(), p)
1315    || anyResultsMatch(n.getLastChild(), p);
1316  887 default:
1317  887 return p.apply(n);
1318    }
1319    }
1320   
 
1321    static class NumbericResultPredicate implements Predicate<Node> {
 
1322  967 toggle @Override
1323    public boolean apply(Node n) {
1324  967 return isNumericResultHelper(n);
1325    }
1326    }
1327   
1328    static final NumbericResultPredicate NUMBERIC_RESULT_PREDICATE =
1329    new NumbericResultPredicate();
1330   
1331    /**
1332    * Returns true if the result of node evaluation is always a number
1333    */
 
1334  967 toggle static boolean isNumericResult(Node n) {
1335  967 return allResultsMatch(n, NUMBERIC_RESULT_PREDICATE);
1336    }
1337   
 
1338  967 toggle static boolean isNumericResultHelper(Node n) {
1339  967 switch (n.getType()) {
1340  265 case Token.ADD:
1341  265 return !mayBeString(n.getFirstChild())
1342    && !mayBeString(n.getLastChild());
1343  0 case Token.BITNOT:
1344  0 case Token.BITOR:
1345  0 case Token.BITXOR:
1346  0 case Token.BITAND:
1347  1 case Token.LSH:
1348  1 case Token.RSH:
1349  1 case Token.URSH:
1350  112 case Token.SUB:
1351  0 case Token.MUL:
1352  0 case Token.MOD:
1353  0 case Token.DIV:
1354  0 case Token.INC:
1355  0 case Token.DEC:
1356  2 case Token.POS:
1357  1 case Token.NEG:
1358  221 case Token.NUMBER:
1359  339 return true;
1360  153 case Token.NAME:
1361  153 String name = n.getString();
1362  153 if (name.equals("NaN")) {
1363  20 return true;
1364    }
1365  133 if (name.equals("Infinity")) {
1366  10 return true;
1367    }
1368  123 return false;
1369  210 default:
1370  210 return false;
1371    }
1372    }
1373   
 
1374    static class BooleanResultPredicate implements Predicate<Node> {
 
1375  574 toggle @Override
1376    public boolean apply(Node n) {
1377  574 return isBooleanResultHelper(n);
1378    }
1379    }
1380   
1381    static final BooleanResultPredicate BOOLEAN_RESULT_PREDICATE =
1382    new BooleanResultPredicate();
1383   
1384    /**
1385    * @return Whether the result of node evaluation is always a boolean
1386    */
 
1387  571 toggle static boolean isBooleanResult(Node n) {
1388  571 return allResultsMatch(n, BOOLEAN_RESULT_PREDICATE);
1389    }
1390   
 
1391  574 toggle static boolean isBooleanResultHelper(Node n) {
1392  574 switch (n.getType()) {
1393    // Primitives
1394  11 case Token.TRUE:
1395  7 case Token.FALSE:
1396    // Comparisons
1397  2 case Token.EQ:
1398  2 case Token.NE:
1399  2 case Token.SHEQ:
1400  2 case Token.SHNE:
1401  2 case Token.LT:
1402  2 case Token.GT:
1403  2 case Token.LE:
1404  2 case Token.GE:
1405    // Queries
1406  2 case Token.IN:
1407  2 case Token.INSTANCEOF:
1408    // Inversion
1409  0 case Token.NOT:
1410    // delete operator returns a boolean.
1411  1 case Token.DELPROP:
1412  39 return true;
1413  535 default:
1414  535 return false;
1415    }
1416    }
1417   
1418   
1419   
 
1420    static class MayBeStringResultPredicate implements Predicate<Node> {
 
1421  887 toggle @Override
1422    public boolean apply(Node n) {
1423  887 return mayBeStringHelper(n);
1424    }
1425    }
1426   
1427    static final MayBeStringResultPredicate MAY_BE_STRING_PREDICATE =
1428    new MayBeStringResultPredicate();
1429   
1430    /**
1431    * @returns Whether the results is possibly a string.
1432    */
 
1433  688 toggle static boolean mayBeString(Node n) {
1434  688 return mayBeString(n, true);
1435    }
1436   
 
1437  938 toggle static boolean mayBeString(Node n, boolean recurse) {
1438  938 if (recurse) {
1439  868 return anyResultsMatch(n, MAY_BE_STRING_PREDICATE);
1440    } else {
1441  70 return mayBeStringHelper(n);
1442    }
1443    }
1444   
 
1445  957 toggle static boolean mayBeStringHelper(Node n) {
1446  957 return !isNumericResult(n) && !isBooleanResult(n)
1447    && !isUndefined(n) && !n.isNull();
1448    }
1449   
1450    /**
1451    * Returns true if the operator is associative.
1452    * e.g. (a * b) * c = a * (b * c)
1453    * Note: "+" is not associative because it is also the concatenation
1454    * for strings. e.g. "a" + (1 + 2) is not "a" + 1 + 2
1455    */
 
1456  540 toggle static boolean isAssociative(int type) {
1457  540 switch (type) {
1458  50 case Token.MUL:
1459  103 case Token.AND:
1460  27 case Token.OR:
1461  33 case Token.BITOR:
1462  24 case Token.BITXOR:
1463  24 case Token.BITAND:
1464  261 return true;
1465  279 default:
1466  279 return false;
1467    }
1468    }
1469   
1470    /**
1471    * Returns true if the operator is commutative.
1472    * e.g. (a * b) * c = c * (b * a)
1473    * Note 1: "+" is not commutative because it is also the concatenation
1474    * for strings. e.g. "a" + (1 + 2) is not "a" + 1 + 2
1475    * Note 2: only operations on literals and pure functions are commutative.
1476    */
 
1477  137 toggle static boolean isCommutative(int type) {
1478  137 switch (type) {
1479  51 case Token.MUL:
1480  33 case Token.BITOR:
1481  24 case Token.BITXOR:
1482  24 case Token.BITAND:
1483  132 return true;
1484  5 default:
1485  5 return false;
1486    }
1487    }
1488   
 
1489  62816 toggle static boolean isAssignmentOp(Node n) {
1490  62816 switch (n.getType()){
1491  16532 case Token.ASSIGN:
1492  104 case Token.ASSIGN_BITOR:
1493  0 case Token.ASSIGN_BITXOR:
1494  0 case Token.ASSIGN_BITAND:
1495  0 case Token.ASSIGN_LSH:
1496  0 case Token.ASSIGN_RSH:
1497  0 case Token.ASSIGN_URSH:
1498  227 case Token.ASSIGN_ADD:
1499  54 case Token.ASSIGN_SUB:
1500  55 case Token.ASSIGN_MUL:
1501  6 case Token.ASSIGN_DIV:
1502  5 case Token.ASSIGN_MOD:
1503  16983 return true;
1504    }
1505  45833 return false;
1506    }
1507   
 
1508  19 toggle static int getOpFromAssignmentOp(Node n) {
1509  19 switch (n.getType()){
1510  0 case Token.ASSIGN_BITOR:
1511  0 return Token.BITOR;
1512  0 case Token.ASSIGN_BITXOR:
1513  0 return Token.BITXOR;
1514  0 case Token.ASSIGN_BITAND:
1515  0 return Token.BITAND;
1516  0 case Token.ASSIGN_LSH:
1517  0 return Token.LSH;
1518  0 case Token.ASSIGN_RSH:
1519  0 return Token.RSH;
1520  0 case Token.ASSIGN_URSH:
1521  0 return Token.URSH;
1522  14 case Token.ASSIGN_ADD:
1523  14 return Token.ADD;
1524  1 case Token.ASSIGN_SUB:
1525  1 return Token.SUB;
1526  4 case Token.ASSIGN_MUL:
1527  4 return Token.MUL;
1528  0 case Token.ASSIGN_DIV:
1529  0 return Token.DIV;
1530  0 case Token.ASSIGN_MOD:
1531  0 return Token.MOD;
1532    }
1533  0 throw new IllegalArgumentException("Not an assignment op:" + n);
1534    }
1535   
1536    /**
1537    * Determines if the given node contains a function statement or function
1538    * expression.
1539    */
 
1540  315 toggle static boolean containsFunction(Node n) {
1541  315 return containsType(n, Token.FUNCTION);
1542    }
1543   
1544    /**
1545    * Returns true if the shallow scope contains references to 'this' keyword
1546    */
 
1547  191 toggle static boolean referencesThis(Node n) {
1548  191 Node start = (n.isFunction()) ? n.getLastChild() : n;
1549  191 return containsType(start, Token.THIS, MATCH_NOT_FUNCTION);
1550    }
1551   
1552    /**
1553    * Is this a GETPROP or GETELEM node?
1554    */
 
1555  30199 toggle static boolean isGet(Node n) {
1556  30199 return n.isGetProp() || n.isGetElem();
1557    }
1558   
1559    /**
1560    * Is this node the name of a variable being declared?
1561    *
1562    * @param n The node
1563    * @return True if {@code n} is NAME and {@code parent} is VAR
1564    */
 
1565  200271 toggle static boolean isVarDeclaration(Node n) {
1566    // There is no need to verify that parent != null because a NAME node
1567    // always has a parent in a valid parse tree.
1568  200271 return n.isName() && n.getParent().isVar();
1569    }
1570   
1571    /**
1572    * For an assignment or variable declaration get the assigned value.
1573    * @return The value node representing the new value.
1574    */
 
1575  740 toggle static Node getAssignedValue(Node n) {
1576  740 Preconditions.checkState(n.isName());
1577  740 Node parent = n.getParent();
1578  740 if (parent.isVar()) {
1579  474 return n.getFirstChild();
1580  266 } else if (parent.isAssign() && parent.getFirstChild() == n) {
1581  230 return n.getNext();
1582    } else {
1583  36 return null;
1584    }
1585    }
1586   
1587    /**
1588    * Is this node an assignment expression statement?
1589    *
1590    * @param n The node
1591    * @return True if {@code n} is EXPR_RESULT and {@code n}'s
1592    * first child is ASSIGN
1593    */
 
1594  98743 toggle static boolean isExprAssign(Node n) {
1595  98743 return n.isExprResult()
1596    && n.getFirstChild().isAssign();
1597    }
1598   
1599    /**
1600    * Is this node a call expression statement?
1601    *
1602    * @param n The node
1603    * @return True if {@code n} is EXPR_RESULT and {@code n}'s
1604    * first child is CALL
1605    */
 
1606  1546 toggle static boolean isExprCall(Node n) {
1607  1546 return n.isExprResult()
1608    && n.getFirstChild().isCall();
1609    }
1610   
1611    /**
1612    * @return Whether the node represents a FOR-IN loop.
1613    */
 
1614  9382 toggle static boolean isForIn(Node n) {
1615  9382 return n.isFor()
1616    && n.getChildCount() == 3;
1617    }
1618   
1619    /**
1620    * Determines whether the given node is a FOR, DO, or WHILE node.
1621    */
 
1622  1598 toggle static boolean isLoopStructure(Node n) {
1623  1598 switch (n.getType()) {
1624  12 case Token.FOR:
1625  3 case Token.DO:
1626  5 case Token.WHILE:
1627  20 return true;
1628  1578 default:
1629  1578 return false;
1630    }
1631    }
1632   
1633    /**
1634    * @param n The node to inspect.
1635    * @return If the node, is a FOR, WHILE, or DO, it returns the node for
1636    * the code BLOCK, null otherwise.
1637    */
 
1638  47 toggle static Node getLoopCodeBlock(Node n) {
1639  47 switch (n.getType()) {
1640  17 case Token.FOR:
1641  11 case Token.WHILE:
1642  28 return n.getLastChild();
1643  19 case Token.DO:
1644  19 return n.getFirstChild();
1645  0 default:
1646  0 return null;
1647    }
1648    }
1649   
1650    /**
1651    * @return Whether the specified node has a loop parent that
1652    * is within the current scope.
1653    */
 
1654  106 toggle static boolean isWithinLoop(Node n) {
1655  106 for (Node parent : n.getAncestors()) {
1656  427 if (NodeUtil.isLoopStructure(parent)) {
1657  7 return true;
1658    }
1659   
1660  420 if (parent.isFunction()) {
1661  58 break;
1662    }
1663    }
1664  99 return false;
1665    }
1666   
1667    /**
1668    * Determines whether the given node is a FOR, DO, WHILE, WITH, or IF node.
1669    */
 
1670  164082 toggle static boolean isControlStructure(Node n) {
1671  164082 switch (n.getType()) {
1672  927 case Token.FOR:
1673  108 case Token.DO:
1674  49 case Token.WHILE:
1675  66 case Token.WITH:
1676  1871 case Token.IF:
1677  1033 case Token.LABEL:
1678  238 case Token.TRY:
1679  10 case Token.CATCH:
1680  95 case Token.SWITCH:
1681  76 case Token.CASE:
1682  16 case Token.DEFAULT_CASE:
1683  4489 return true;
1684  159593 default:
1685  159593 return false;
1686    }
1687    }
1688   
1689    /**
1690    * Determines whether the given node is code node for FOR, DO,
1691    * WHILE, WITH, or IF node.
1692    */
 
1693  14 toggle static boolean isControlStructureCodeBlock(Node parent, Node n) {
1694  14 switch (parent.getType()) {
1695  0 case Token.FOR:
1696  2 case Token.WHILE:
1697  0 case Token.LABEL:
1698  0 case Token.WITH:
1699  2 return parent.getLastChild() == n;
1700  9 case Token.DO:
1701  9 return parent.getFirstChild() == n;
1702  3 case Token.IF:
1703  3 return parent.getFirstChild() != n;
1704  0 case Token.TRY:
1705  0 return parent.getFirstChild() == n || parent.getLastChild() == n;
1706  0 case Token.CATCH:
1707  0 return parent.getLastChild() == n;
1708  0 case Token.SWITCH:
1709  0 case Token.CASE:
1710  0 return parent.getFirstChild() != n;
1711  0 case Token.DEFAULT_CASE:
1712  0 return true;
1713  0 default:
1714  0 Preconditions.checkState(isControlStructure(parent));
1715  0 return false;
1716    }
1717    }
1718   
1719    /**
1720    * Gets the condition of an ON_TRUE / ON_FALSE CFG edge.
1721    * @param n a node with an outgoing conditional CFG edge
1722    * @return the condition node or null if the condition is not obviously a node
1723    */
 
1724  759 toggle static Node getConditionExpression(Node n) {
1725  759 switch (n.getType()) {
1726  304 case Token.IF:
1727  213 case Token.WHILE:
1728  517 return n.getFirstChild();
1729  96 case Token.DO:
1730  96 return n.getLastChild();
1731  139 case Token.FOR:
1732  139 switch (n.getChildCount()) {
1733  19 case 3:
1734  19 return null;
1735  120 case 4:
1736  120 return n.getFirstChild().getNext();
1737    }
1738  0 throw new IllegalArgumentException("malformed 'for' statement " + n);
1739  7 case Token.CASE:
1740  7 return null;
1741    }
1742  0 throw new IllegalArgumentException(n + " does not have a condition.");
1743    }
1744   
1745    /**
1746    * @return Whether the node is of a type that contain other statements.
1747    */
 
1748  474731 toggle static boolean isStatementBlock(Node n) {
1749  474731 return n.isScript() || n.isBlock();
1750    }
1751   
1752    /**
1753    * @return Whether the node is used as a statement.
1754    */
 
1755  282540 toggle static boolean isStatement(Node n) {
1756  282540 return isStatementParent(n.getParent());
1757    }
1758   
 
1759  345698 toggle static boolean isStatementParent(Node parent) {
1760    // It is not possible to determine definitely if a node is a statement
1761    // or not if it is not part of the AST. A FUNCTION node can be
1762    // either part of an expression or a statement.
1763  345698 Preconditions.checkState(parent != null);
1764  345698 switch (parent.getType()) {
1765  156019 case Token.SCRIPT:
1766  11297 case Token.BLOCK:
1767  23 case Token.LABEL:
1768  167339 return true;
1769  178359 default:
1770  178359 return false;
1771    }
1772    }
1773   
1774    /** Whether the node is part of a switch statement. */
 
1775  12 toggle static boolean isSwitchCase(Node n) {
1776  12 return n.isCase() || n.isDefaultCase();
1777    }
1778   
1779    /**
1780    * @return Whether the name is a reference to a variable, function or
1781    * function parameter (not a label or a empty function expression name).
1782    */
 
1783  3996 toggle static boolean isReferenceName(Node n) {
1784  3996 return n.isName() && !n.getString().isEmpty();
1785    }
1786   
1787    /** Whether the child node is the FINALLY block of a try. */
 
1788  482 toggle static boolean isTryFinallyNode(Node parent, Node child) {
1789  482 return parent.isTry() && parent.getChildCount() == 3
1790    && child == parent.getLastChild();
1791    }
1792   
1793    /** Whether the node is a CATCH container BLOCK. */
 
1794  411 toggle static boolean isTryCatchNodeContainer(Node n) {
1795  411 Node parent = n.getParent();
1796  411 return parent.isTry()
1797    && parent.getFirstChild().getNext() == n;
1798    }
1799   
1800    /** Safely remove children while maintaining a valid node structure. */
 
1801  417 toggle static void removeChild(Node parent, Node node) {
1802  417 if (isTryFinallyNode(parent, node)) {
1803  1 if (NodeUtil.hasCatchHandler(getCatchBlock(parent))) {
1804    // A finally can only be removed if there is a catch.
1805  1 parent.removeChild(node);
1806    } else {
1807    // Otherwise, only its children can be removed.
1808  0 node.detachChildren();
1809    }
1810  416 } else if (node.isCatch()) {
1811    // The CATCH can can only be removed if there is a finally clause.
1812  5 Node tryNode = node.getParent().getParent();
1813  5 Preconditions.checkState(NodeUtil.hasFinally(tryNode));
1814  5 node.detachFromParent();
1815  411 } else if (isTryCatchNodeContainer(node)) {
1816    // The container node itself can't be removed, but the contained CATCH
1817    // can if there is a 'finally' clause
1818  1 Node tryNode = node.getParent();
1819  1 Preconditions.checkState(NodeUtil.hasFinally(tryNode));
1820  1 node.detachChildren();
1821  410 } else if (node.isBlock()) {
1822    // Simply empty the block. This maintains source location and
1823    // "synthetic"-ness.
1824  3 node.detachChildren();
1825  407 } else if (isStatementBlock(parent)
1826    || isSwitchCase(node)) {
1827    // A statement in a block can simply be removed.
1828  395 parent.removeChild(node);
1829  12 } else if (parent.isVar()) {
1830  4 if (parent.hasMoreThanOneChild()) {
1831  3 parent.removeChild(node);
1832    } else {
1833    // Remove the node from the parent, so it can be reused.
1834  1 parent.removeChild(node);
1835    // This would leave an empty VAR, remove the VAR itself.
1836  1 removeChild(parent.getParent(), parent);
1837    }
1838  8 } else if (parent.isLabel()
1839    && node == parent.getLastChild()) {
1840    // Remove the node from the parent, so it can be reused.
1841  5 parent.removeChild(node);
1842    // A LABEL without children can not be referred to, remove it.
1843  5 removeChild(parent.getParent(), parent);
1844  3 } else if (parent.isFor()
1845    && parent.getChildCount() == 4) {
1846    // Only Token.FOR can have an Token.EMPTY other control structure
1847    // need something for the condition. Others need to be replaced
1848    // or the structure removed.
1849  3 parent.replaceChild(node, IR.empty());
1850    } else {
1851  0 throw new IllegalStateException("Invalid attempt to remove node: " +
1852    node.toString() + " of " + parent.toString());
1853    }
1854    }
1855   
1856    /**
1857    * Add a finally block if one does not exist.
1858    */
 
1859  4 toggle static void maybeAddFinally(Node tryNode) {
1860  4 Preconditions.checkState(tryNode.isTry());
1861  4 if (!NodeUtil.hasFinally(tryNode)) {
1862  2 tryNode.addChildrenToBack(IR.block().srcref(tryNode));
1863    }
1864    }
1865   
1866    /**
1867    * Merge a block with its parent block.
1868    * @return Whether the block was removed.
1869    */
 
1870  623 toggle static boolean tryMergeBlock(Node block) {
1871  623 Preconditions.checkState(block.isBlock());
1872  623 Node parent = block.getParent();
1873    // Try to remove the block if its parent is a block/script or if its
1874    // parent is label and it has exactly one child.
1875  623 if (isStatementBlock(parent)) {
1876  102 Node previous = block;
1877  222 while (block.hasChildren()) {
1878  120 Node child = block.removeFirstChild();
1879  120 parent.addChildAfter(child, previous);
1880  120 previous = child;
1881    }
1882  102 parent.removeChild(block);
1883  102 return true;
1884    } else {
1885  521 return false;
1886    }
1887    }
1888   
1889    /**
1890    * @param node A node
1891    * @return Whether the call is a NEW or CALL node.
1892    */
 
1893  10224 toggle static boolean isCallOrNew(Node node) {
1894  10224 return node.isCall() || node.isNew();
1895    }
1896   
1897    /**
1898    * Return a BLOCK node for the given FUNCTION node.
1899    */
 
1900  846 toggle static Node getFunctionBody(Node fn) {
1901  846 Preconditions.checkArgument(fn.isFunction());
1902  846 return fn.getLastChild();
1903    }
1904   
1905    /**
1906    * Is this node a function declaration? A function declaration is a function
1907    * that has a name that is added to the current scope (i.e. a function that
1908    * is not part of a expression; see {@link #isFunctionExpression}).
1909    */
 
1910  217735 toggle static boolean isFunctionDeclaration(Node n) {
1911  217735 return n.isFunction() && isStatement(n);
1912    }
1913   
1914    /**
1915    * Is this node a hoisted function declaration? A function declaration in the
1916    * scope root is hoisted to the top of the scope.
1917    * See {@link #isFunctionDeclaration}).
1918    */
 
1919  24340 toggle static boolean isHoistedFunctionDeclaration(Node n) {
1920  24340 return isFunctionDeclaration(n)
1921    && (n.getParent().isScript()
1922    || n.getParent().getParent().isFunction());
1923    }
1924   
1925    /**
1926    * Is a FUNCTION node an function expression? An function expression is one
1927    * that has either no name or a name that is not added to the current scope.
1928    *
1929    * <p>Some examples of function expressions:
1930    * <pre>
1931    * (function () {})
1932    * (function f() {})()
1933    * [ function f() {} ]
1934    * var f = function f() {};
1935    * for (function f() {};;) {}
1936    * </pre>
1937    *
1938    * <p>Some examples of functions that are <em>not</em> expressions:
1939    * <pre>
1940    * function f() {}
1941    * if (x); else function f() {}
1942    * for (;;) { function f() {} }
1943    * </pre>
1944    *
1945    * @param n A node
1946    * @return Whether n is an function used within an expression.
1947    */
 
1948  184521 toggle static boolean isFunctionExpression(Node n) {
1949  184521 return n.isFunction() && !isStatement(n);
1950    }
1951   
1952    /**
1953    * Returns whether this is a bleeding function (an anonymous named function
1954    * that bleeds into the inner scope).
1955    */
 
1956  5101 toggle static boolean isBleedingFunctionName(Node n) {
1957  5101 return n.isName() && !n.getString().isEmpty() &&
1958    isFunctionExpression(n.getParent());
1959    }
1960   
1961    /**
1962    * Determines if a node is a function expression that has an empty body.
1963    *
1964    * @param node a node
1965    * @return whether the given node is a function expression that is empty
1966    */
 
1967  934 toggle static boolean isEmptyFunctionExpression(Node node) {
1968  934 return isFunctionExpression(node) && isEmptyBlock(node.getLastChild());
1969    }
1970   
1971    /**
1972    * Determines if a function takes a variable number of arguments by
1973    * looking for references to the "arguments" var_args object.
1974    */
 
1975  352 toggle static boolean isVarArgsFunction(Node function) {
1976    // TODO(johnlenz): rename this function
1977  352 Preconditions.checkArgument(function.isFunction());
1978  352 return isNameReferenced(
1979    function.getLastChild(),
1980    "arguments",
1981    MATCH_NOT_FUNCTION);
1982    }
1983   
1984    /**
1985    * @return Whether node is a call to methodName.
1986    * a.f(...)
1987    * a['f'](...)
1988    */
 
1989  1284 toggle static boolean isObjectCallMethod(Node callNode, String methodName) {
1990  1284 if (callNode.isCall()) {
1991  1182 Node functionIndentifyingExpression = callNode.getFirstChild();
1992  1182 if (isGet(functionIndentifyingExpression)) {
1993  219 Node last = functionIndentifyingExpression.getLastChild();
1994  219 if (last != null && last.isString()) {
1995  219 String propName = last.getString();
1996  219 return (propName.equals(methodName));
1997    }
1998    }
1999    }
2000  1065 return false;
2001    }
2002   
2003   
2004    /**
2005    * @return Whether the callNode represents an expression in the form of:
2006    * x.call(...)
2007    * x['call'](...)
2008    */
 
2009  859 toggle static boolean isFunctionObjectCall(Node callNode) {
2010  859 return isObjectCallMethod(callNode, "call");
2011    }
2012   
2013    /**
2014    * @return Whether the callNode represents an expression in the form of:
2015    * x.apply(...)
2016    * x['apply'](...)
2017    */
 
2018  425 toggle static boolean isFunctionObjectApply(Node callNode) {
2019  425 return isObjectCallMethod(callNode, "apply");
2020    }
2021   
2022    /**
2023    * Determines whether this node is strictly on the left hand side of an assign
2024    * or var initialization. Notably, this does not include all L-values, only
2025    * statements where the node is used only as an L-value.
2026    *
2027    * @param n The node
2028    * @param parent Parent of the node
2029    * @return True if n is the left hand of an assign
2030    */
 
2031  1036 toggle static boolean isVarOrSimpleAssignLhs(Node n, Node parent) {
2032  1036 return (parent.isAssign() && parent.getFirstChild() == n) ||
2033    parent.isVar();
2034    }
2035   
2036    /**
2037    * Determines whether this node is used as an L-value. Notice that sometimes
2038    * names are used as both L-values and R-values.
2039    *
2040    * We treat "var x;" as a pseudo-L-value, which kind of makes sense if you
2041    * treat it as "assignment to 'undefined' at the top of the scope". But if
2042    * we're honest with ourselves, it doesn't make sense, and we only do this
2043    * because it makes sense to treat this as syntactically similar to
2044    * "var x = 0;".
2045    *
2046    * @param n The node
2047    * @return True if n is an L-value.
2048    */
 
2049  6366 toggle public static boolean isLValue(Node n) {
2050  6366 Preconditions.checkArgument(n.isName() || n.isGetProp() ||
2051    n.isGetElem());
2052  6366 Node parent = n.getParent();
2053  6366 if (parent == null) {
2054  0 return false;
2055    }
2056  6366 return (NodeUtil.isAssignmentOp(parent) && parent.getFirstChild() == n)
2057    || (NodeUtil.isForIn(parent) && parent.getFirstChild() == n)
2058    || parent.isVar()
2059    || (parent.isFunction() && parent.getFirstChild() == n)
2060    || parent.isDec()
2061    || parent.isInc()
2062    || parent.isParamList()
2063    || parent.isCatch();
2064    }
2065   
2066    /**
2067    * Determines whether a node represents an object literal key
2068    * (e.g. key1 in {key1: value1, key2: value2}).
2069    *
2070    * @param node A node
2071    * @param parent The node's parent
2072    */
 
2073  230078 toggle static boolean isObjectLitKey(Node node, Node parent) {
2074  230078 switch (node.getType()) {
2075  2297 case Token.STRING_KEY:
2076  122 case Token.GETTER_DEF:
2077  99 case Token.SETTER_DEF:
2078  2518 return true;
2079    }
2080  227560 return false;
2081    }
2082   
2083    /**
2084    * Get the name of an object literal key.
2085    *
2086    * @param key A node
2087    */
 
2088  841 toggle static String getObjectLitKeyName(Node key) {
2089  841 switch (key.getType()) {
2090  744 case Token.STRING_KEY:
2091  49 case Token.GETTER_DEF:
2092  48 case Token.SETTER_DEF:
2093  841 return key.getString();
2094    }
2095  0 throw new IllegalStateException("Unexpected node type: " + key);
2096    }
2097   
2098    /**
2099    * @param key A OBJECTLIT key node.
2100    * @return The type expected when using the key.
2101    */
 
2102  318 toggle static JSType getObjectLitKeyTypeFromValueType(Node key, JSType valueType) {
2103  318 if (valueType != null) {
2104  209 switch (key.getType()) {
2105  15 case Token.GETTER_DEF:
2106    // GET must always return a function type.
2107  15 if (valueType.isFunctionType()) {
2108  14 FunctionType fntype = valueType.toMaybeFunctionType();
2109  14 valueType = fntype.getReturnType();
2110    } else {
2111  1 return null;
2112    }
2113  14 break;
2114  19 case Token.SETTER_DEF:
2115  19 if (valueType.isFunctionType()) {
2116    // SET must always return a function type.
2117  18 FunctionType fntype = valueType.toMaybeFunctionType();
2118  18 Node param = fntype.getParametersNode().getFirstChild();
2119    // SET function must always have one parameter.
2120  18 valueType = param.getJSType();
2121    } else {
2122  1 return null;
2123    }
2124  18 break;
2125    }
2126    }
2127  316 return valueType;
2128    }
2129   
2130    /**
2131    * Determines whether a node represents an object literal get or set key
2132    * (e.g. key1 in {get key1() {}, set key2(a){}).
2133    *
2134    * @param node A node
2135    */
 
2136  364 toggle static boolean isGetOrSetKey(Node node) {
2137  364 switch (node.getType()) {
2138  40 case Token.GETTER_DEF:
2139  2 case Token.SETTER_DEF:
2140  42 return true;
2141    }
2142  322 return false;
2143    }
2144   
2145    /**
2146    * Converts an operator's token value (see {@link Token}) to a string
2147    * representation.
2148    *
2149    * @param operator the operator's token value to convert
2150    * @return the string representation or {@code null} if the token value is
2151    * not an operator
2152    */
 
2153  364451 toggle static String opToStr(int operator) {
2154  364451 switch (operator) {
2155  177 case Token.BITOR: return "|";
2156  451 case Token.OR: return "||";
2157  163 case Token.BITXOR: return "^";
2158  908 case Token.AND: return "&&";
2159  163 case Token.BITAND: return "&";
2160  1319 case Token.SHEQ: return "===";
2161  1480 case Token.EQ: return "==";
2162  4376 case Token.NOT: return "!";
2163  1237 case Token.NE: return "!=";
2164  1195 case Token.SHNE: return "!==";
2165  25 case Token.LSH: return "<<";
2166  45 case Token.IN: return "in";
2167  421 case Token.LE: return "<=";
2168  903 case Token.LT: return "<";
2169  12 case Token.URSH: return ">>>";
2170  17 case Token.RSH: return ">>";
2171  434 case Token.GE: return ">=";
2172  561 case Token.GT: return ">";
2173  355 case Token.MUL: return "*";
2174  71 case Token.DIV: return "/";
2175  7 case Token.MOD: return "%";
2176  45 case Token.BITNOT: return "~";
2177  1433 case Token.ADD: return "+";
2178  187 case Token.SUB: return "-";
2179  52 case Token.POS: return "+";
2180  2428 case Token.NEG: return "-";
2181  13280 case Token.ASSIGN: return "=";
2182  103 case Token.ASSIGN_BITOR: return "|=";
2183  0 case Token.ASSIGN_BITXOR: return "^=";
2184  0 case Token.ASSIGN_BITAND: return "&=";
2185  0 case Token.ASSIGN_LSH: return "<<=";
2186  0 case Token.ASSIGN_RSH: return ">>=";
2187  0 case Token.ASSIGN_URSH: return ">>>=";
2188  126 case Token.ASSIGN_ADD: return "+=";
2189  38 case Token.ASSIGN_SUB: return "-=";
2190  29 case Token.ASSIGN_MUL: return "*=";
2191  6 case Token.ASSIGN_DIV: return "/=";
2192  4 case Token.ASSIGN_MOD: return "%=";
2193  1204 case Token.VOID: return "void";
2194  404 case Token.TYPEOF: return "typeof";
2195  122 case Token.INSTANCEOF: return "instanceof";
2196  330670 default: return null;
2197    }
2198    }
2199   
2200    /**
2201    * Converts an operator's token value (see {@link Token}) to a string
2202    * representation or fails.
2203    *
2204    * @param operator the operator's token value to convert
2205    * @return the string representation
2206    * @throws Error if the token value is not an operator
2207    */
 
2208  4254 toggle static String opToStrNoFail(int operator) {
2209  4254 String res = opToStr(operator);
2210  4254 if (res == null) {
2211  0 throw new Error("Unknown op " + operator + ": " +
2212    Token.name(operator));
2213    }
2214  4254 return res;
2215    }
2216   
2217    /**
2218    * @return true if n or any of its children are of the specified type
2219    */
 
2220  2408 toggle static boolean containsType(Node node,
2221    int type,
2222    Predicate<Node> traverseChildrenPred) {
2223  2408 return has(node, new MatchNodeType(type), traverseChildrenPred);
2224    }
2225   
2226    /**
2227    * @return true if n or any of its children are of the specified type
2228    */
 
2229  329 toggle static boolean containsType(Node node, int type) {
2230  329 return containsType(node, type, Predicates.<Node>alwaysTrue());
2231    }
2232   
2233   
2234    /**
2235    * Given a node tree, finds all the VAR declarations in that tree that are
2236    * not in an inner scope. Then adds a new VAR node at the top of the current
2237    * scope that redeclares them, if necessary.
2238    */
 
2239  86 toggle static void redeclareVarsInsideBranch(Node branch) {
2240  86 Collection<Node> vars = getVarsDeclaredInBranch(branch);
2241  86 if (vars.isEmpty()) {
2242  77 return;
2243    }
2244   
2245  9 Node parent = getAddingRoot(branch);
2246  9 for (Node nameNode : vars) {
2247  10 Node var = IR.var(
2248    IR.name(nameNode.getString())
2249    .srcref(nameNode))
2250    .srcref(nameNode);
2251  10 copyNameAnnotations(nameNode, var.getFirstChild());
2252  10 parent.addChildToFront(var);
2253    }
2254    }
2255   
2256    /**
2257    * Copy any annotations that follow a named value.
2258    * @param source
2259    * @param destination
2260    */
 
2261  90 toggle static void copyNameAnnotations(Node source, Node destination) {
2262  90 if (source.getBooleanProp(Node.IS_CONSTANT_NAME)) {
2263  13 destination.putBooleanProp(Node.IS_CONSTANT_NAME, true);
2264    }
2265    }
2266   
2267    /**
2268    * Gets a Node at the top of the current scope where we can add new var
2269    * declarations as children.
2270    */
 
2271  9 toggle private static Node getAddingRoot(Node n) {
2272  9 Node addingRoot = null;
2273  9 Node ancestor = n;
2274  ? while (null != (ancestor = ancestor.getParent())) {
2275  16 int type = ancestor.getType();
2276  16 if (type == Token.SCRIPT) {
2277  7 addingRoot = ancestor;
2278  7 break;
2279  9 } else if (type == Token.FUNCTION) {
2280  2 addingRoot = ancestor.getLastChild();
2281  2 break;
2282    }
2283    }
2284   
2285    // make sure that the adding root looks ok
2286  9 Preconditions.checkState(addingRoot.isBlock() ||
2287    addingRoot.isScript());
2288  9 Preconditions.checkState(addingRoot.getFirstChild() == null ||
2289    !addingRoot.getFirstChild().isScript());
2290  9 return addingRoot;
2291    }
2292   
2293    /**
2294    * Creates a node representing a qualified name.
2295    *
2296    * @param name A qualified name (e.g. "foo" or "foo.bar.baz")
2297    * @return A NAME or GETPROP node
2298    */
 
2299  161 toggle public static Node newQualifiedNameNode(
2300    CodingConvention convention, String name) {
2301  161 int endPos = name.indexOf('.');
2302  161 if (endPos == -1) {
2303  29 return newName(convention, name);
2304    }
2305  132 Node node = newName(convention, name.substring(0, endPos));
2306  132 int startPos;
2307  132 do {
2308  184 startPos = endPos + 1;
2309  184 endPos = name.indexOf('.', startPos);
2310  184 String part = (endPos == -1
2311    ? name.substring(startPos)
2312    : name.substring(startPos, endPos));
2313  184 Node propNode = IR.string(part);
2314  184 if (convention.isConstantKey(part)) {
2315  8 propNode.putBooleanProp(Node.IS_CONSTANT_NAME, true);
2316    }
2317  184 node = IR.getprop(node, propNode);
2318  184 } while (endPos != -1);
2319   
2320  132 return node;
2321    }
2322   
2323    /**
2324    * Creates a node representing a qualified name, copying over the source
2325    * location information from the basis node and assigning the given original
2326    * name to the node.
2327    *
2328    * @param name A qualified name (e.g. "foo" or "foo.bar.baz")
2329    * @param basisNode The node that represents the name as currently found in
2330    * the AST.
2331    * @param originalName The original name of the item being represented by the
2332    * NAME node. Used for debugging information.
2333    *
2334    * @return A NAME or GETPROP node
2335    */
 
2336  113 toggle static Node newQualifiedNameNode(
2337    CodingConvention convention, String name, Node basisNode,
2338    String originalName) {
2339  113 Node node = newQualifiedNameNode(convention, name);
2340  113 setDebugInformation(node, basisNode, originalName);
2341  113 return node;
2342    }
2343   
2344    /**
2345    * Gets the root node of a qualified name. Must be either NAME or THIS.
2346    */
 
2347  405 toggle static Node getRootOfQualifiedName(Node qName) {
2348  405 for (Node current = qName; true;
2349    current = current.getFirstChild()) {
2350  826 if (current.isName() || current.isThis()) {
2351  405 return current;
2352    }
2353  421 Preconditions.checkState(current.isGetProp());
2354    }
2355    }
2356   
2357    /**
2358    * Sets the debug information (source file info and original name)
2359    * on the given node.
2360    *
2361    * @param node The node on which to set the debug information.
2362    * @param basisNode The basis node from which to copy the source file info.
2363    * @param originalName The original name of the node.
2364    */
 
2365  150 toggle static void setDebugInformation(Node node, Node basisNode,
2366    String originalName) {
2367  150 node.copyInformationFromForTree(basisNode);
2368  150 node.putProp(Node.ORIGINALNAME_PROP, originalName);
2369    }
2370   
 
2371  360 toggle private static Node newName(
2372    CodingConvention convention, String name) {
2373  360 Node nameNode = IR.name(name);
2374  360 if (convention.isConstant(name)) {
2375  24 nameNode.putBooleanProp(Node.IS_CONSTANT_NAME, true);
2376    }
2377  360 return nameNode;
2378    }
2379   
2380    /**
2381    * Creates a new node representing an *existing* name, copying over the source
2382    * location information from the basis node.
2383    *
2384    * @param name The name for the new NAME node.
2385    * @param srcref The node that represents the name as currently found in
2386    * the AST.
2387    *
2388    * @return The node created.
2389    */
 
2390  199 toggle static Node newName(CodingConvention convention, String name, Node srcref) {
2391  199 return newName(convention, name).srcref(srcref);
2392    }
2393   
2394    /**
2395    * Creates a new node representing an *existing* name, copying over the source
2396    * location information from the basis node and assigning the given original
2397    * name to the node.
2398    *
2399    * @param name The name for the new NAME node.
2400    * @param basisNode The node that represents the name as currently found in
2401    * the AST.
2402    * @param originalName The original name of the item being represented by the
2403    * NAME node. Used for debugging information.
2404    *
2405    * @return The node created.
2406    */
 
2407  197 toggle static Node newName(
2408    CodingConvention convention, String name,
2409    Node basisNode, String originalName) {
2410  197 Node nameNode = newName(convention, name, basisNode);
2411  197 nameNode.putProp(Node.ORIGINALNAME_PROP, originalName);
2412  197 return nameNode;
2413    }
2414   
2415    /** Test if all characters in the string are in the Basic Latin (aka ASCII)
2416    * character set - that they have UTF-16 values equal to or below 0x7f.
2417    * This check can find which identifiers with Unicode characters need to be
2418    * escaped in order to allow resulting files to be processed by non-Unicode
2419    * aware UNIX tools and editors.
2420    * *
2421    * See http://en.wikipedia.org/wiki/Latin_characters_in_Unicode
2422    * for more on Basic Latin.
2423    *
2424    * @param s The string to be checked for ASCII-goodness.
2425    *
2426    * @return True if all characters in the string are in Basic Latin set.
2427    */
 
2428  107217 toggle static boolean isLatin(String s) {
2429  107217 int len = s.length();
2430  951202 for (int index = 0; index < len; index++) {
2431  843995 char c = s.charAt(index);
2432  843995 if (c > LARGEST_BASIC_LATIN) {
2433  10 return false;
2434    }
2435    }
2436  107207 return true;
2437    }
2438   
2439    /**
2440    * Determines whether the given name is a valid variable name.
2441    */
 
2442  203 toggle static boolean isValidSimpleName(String name) {
2443  203 return TokenStream.isJSIdentifier(name) &&
2444    !TokenStream.isKeyword(name) &&
2445    // no Unicode escaped characters - some browsers are less tolerant
2446    // of Unicode characters that might be valid according to the
2447    // language spec.
2448    // Note that by this point, Unicode escapes have been converted
2449    // to UTF-16 characters, so we're only searching for character
2450    // values, not escapes.
2451    isLatin(name);
2452    }
2453   
2454    /**
2455    * Determines whether the given name is a valid qualified name.
2456    */
2457    // TODO(nicksantos): This should be moved into a "Language" API,
2458    // so that the results are different for es5 and es3.
 
2459  9 toggle public static boolean isValidQualifiedName(String name) {
2460  9 if (name.endsWith(".") || name.startsWith(".")) {
2461  2 return false;
2462    }
2463  7 String[] parts = name.split("\\.");
2464  7 for (String part : parts) {
2465  10 if (!isValidSimpleName(part)) {
2466  4 return false;
2467    }
2468    }
2469  3 return true;
2470    }
2471   
2472    /**
2473    * Determines whether the given name can appear on the right side of
2474    * the dot operator. Many properties (like reserved words) cannot.
2475    */
 
2476  184 toggle static boolean isValidPropertyName(String name) {
2477  184 return isValidSimpleName(name);
2478    }
2479   
 
2480    private static class VarCollector implements Visitor {
2481    final Map<String, Node> vars = Maps.newLinkedHashMap();
2482   
 
2483  357 toggle @Override
2484    public void visit(Node n) {
2485  357 if (n.isName()) {
2486  68 Node parent = n.getParent();
2487  68 if (parent != null && parent.isVar()) {
2488  14 String name = n.getString();
2489  14 if (!vars.containsKey(name)) {
2490  14 vars.put(name, n);
2491    }
2492    }
2493    }
2494    }
2495    }
2496   
2497    /**
2498    * Retrieves vars declared in the current node tree, excluding descent scopes.
2499    */
 
2500  91 toggle static Collection<Node> getVarsDeclaredInBranch(Node root) {
2501  91 VarCollector collector = new VarCollector();
2502  91 visitPreOrder(
2503    root,
2504    collector,
2505    MATCH_NOT_FUNCTION);
2506  91 return collector.vars.values();
2507    }
2508   
2509    /**
2510    * @return {@code true} if the node an assignment to a prototype property of
2511    * some constructor.
2512    */
 
2513  202 toggle static boolean isPrototypePropertyDeclaration(Node n) {
2514  202 if (!isExprAssign(n)) {
2515  118 return false;
2516    }
2517  84 return isPrototypeProperty(n.getFirstChild().getFirstChild());
2518    }
2519   
2520    /**
2521    * @return Whether the node represents a qualified prototype property.
2522    */
 
2523  130 toggle static boolean isPrototypeProperty(Node n) {
2524  130 String lhsString = n.getQualifiedName();
2525  130 if (lhsString == null) {
2526  29 return false;
2527    }
2528  101 int prototypeIdx = lhsString.indexOf(".prototype.");
2529  101 return prototypeIdx != -1;
2530    }
2531   
2532    /**
2533    * @return The class name part of a qualified prototype name.
2534    */
 
2535  57 toggle static Node getPrototypeClassName(Node qName) {
2536  57 Node cur = qName;
2537  114 while (cur.isGetProp()) {
2538  114 if (cur.getLastChild().getString().equals("prototype")) {
2539  57 return cur.getFirstChild();
2540    } else {
2541  57 cur = cur.getFirstChild();
2542    }
2543    }
2544  0 return null;
2545    }
2546   
2547    /**
2548    * @return The string property name part of a qualified prototype name.
2549    */
 
2550  57 toggle static String getPrototypePropertyName(Node qName) {
2551  57 String qNameStr = qName.getQualifiedName();
2552  57 int prototypeIdx = qNameStr.lastIndexOf(".prototype.");
2553  57 int memberIndex = prototypeIdx + ".prototype".length() + 1;
2554  57 return qNameStr.substring(memberIndex);
2555    }
2556   
2557    /**
2558    * Create a node for an empty result expression:
2559    * "void 0"
2560    */
 
2561  146 toggle static Node newUndefinedNode(Node srcReferenceNode) {
2562  146 Node node = IR.voidNode(IR.number(0));
2563  146 if (srcReferenceNode != null) {
2564  142 node.copyInformationFromForTree(srcReferenceNode);
2565    }
2566  146 return node;
2567    }
2568   
2569    /**
2570    * Create a VAR node containing the given name and initial value expression.
2571    */
 
2572  123 toggle static Node newVarNode(String name, Node value) {
2573  123 Node nodeName = IR.name(name);
2574  123 if (value != null) {
2575  99 Preconditions.checkState(value.getNext() == null);
2576  99 nodeName.addChildToBack(value);
2577  99 nodeName.srcref(value);
2578    }
2579  123 Node var = IR.var(nodeName).srcref(nodeName);
2580   
2581  123 return var;
2582    }
2583   
2584    /**
2585    * A predicate for matching name nodes with the specified node.
2586    */
 
2587    private static class MatchNameNode implements Predicate<Node>{
2588    final String name;
2589   
 
2590  644 toggle MatchNameNode(String name){
2591  644 this.name = name;
2592    }
2593   
 
2594  3274 toggle @Override
2595    public boolean apply(Node n) {
2596  3274 return n.isName() && n.getString().equals(name);
2597    }
2598    }
2599   
2600    /**
2601    * A predicate for matching nodes with the specified type.
2602    */
 
2603    static class MatchNodeType implements Predicate<Node>{
2604    final int type;
2605   
 
2606  2566 toggle MatchNodeType(int type){
2607  2566 this.type = type;
2608    }
2609   
 
2610  7794 toggle @Override
2611    public boolean apply(Node n) {
2612  7794 return n.getType() == type;
2613    }
2614    }
2615   
2616   
2617    /**
2618    * A predicate for matching var or function declarations.
2619    */
 
2620    static class MatchDeclaration implements Predicate<Node> {
 
2621  234 toggle @Override
2622    public boolean apply(Node n) {
2623  234 return isFunctionDeclaration(n) || n.isVar();
2624    }
2625    }
2626   
2627    /**
2628    * A predicate for matching anything except function nodes.
2629    */
 
2630    private static class MatchNotFunction implements Predicate<Node>{
 
2631  7760 toggle @Override
2632    public boolean apply(Node n) {
2633  7760 return !n.isFunction();
2634    }
2635    }
2636   
2637    static final Predicate<Node> MATCH_NOT_FUNCTION = new MatchNotFunction();
2638   
2639    /**
2640    * A predicate for matching statements without exiting the current scope.
2641    */
 
2642    static class MatchShallowStatement implements Predicate<Node>{
 
2643  783 toggle @Override
2644    public boolean apply(Node n) {
2645  783 Node parent = n.getParent();
2646  783 return n.isBlock()
2647    || (!n.isFunction() && (parent == null
2648    || isControlStructure(parent)
2649    || isStatementBlock(parent)));
2650    }
2651    }
2652   
2653    /**
2654    * Finds the number of times a type is referenced within the node tree.
2655    */
 
2656  132 toggle static int getNodeTypeReferenceCount(
2657    Node node, int type, Predicate<Node> traverseChildrenPred) {
2658  132 return getCount(node, new MatchNodeType(type), traverseChildrenPred);
2659    }
2660   
2661    /**
2662    * Whether a simple name is referenced within the node tree.
2663    */
 
2664  524 toggle static boolean isNameReferenced(Node node,
2665    String name,
2666    Predicate<Node> traverseChildrenPred) {
2667  524 return has(node, new MatchNameNode(name), traverseChildrenPred);
2668    }
2669   
2670    /**
2671    * Whether a simple name is referenced within the node tree.
2672    */
 
2673  7 toggle static boolean isNameReferenced(Node node, String name) {
2674  7 return isNameReferenced(node, name, Predicates.<Node>alwaysTrue());
2675    }
2676   
2677    /**
2678    * Finds the number of times a simple name is referenced within the node tree.
2679    */
 
2680  120 toggle static int getNameReferenceCount(Node node, String name) {
2681  120 return getCount(
2682    node, new MatchNameNode(name), Predicates.<Node>alwaysTrue());
2683    }
2684   
2685    /**
2686    * @return Whether the predicate is true for the node or any of its children.
2687    */
 
2688  13068 toggle static boolean has(Node node,
2689    Predicate<Node> pred,
2690    Predicate<Node> traverseChildrenPred) {
2691  13068 if (pred.apply(node)) {
2692  248 return true;
2693    }
2694   
2695  12820 if (!traverseChildrenPred.apply(node)) {
2696  184 return false;
2697    }
2698   
2699  21566 for (Node c = node.getFirstChild(); c != null; c = c.getNext()) {
2700  9481 if (has(c, pred, traverseChildrenPred)) {
2701  551 return true;
2702    }
2703    }
2704   
2705  12085 return false;
2706    }
2707   
2708    /**
2709    * @return The number of times the the predicate is true for the node
2710    * or any of its children.
2711    */
 
2712  1466 toggle static int getCount(
2713    Node n, Predicate<Node> pred, Predicate<Node> traverseChildrenPred) {
2714  1466 int total = 0;
2715   
2716  1466 if (pred.apply(n)) {
2717  104 total++;
2718    }
2719   
2720  1466 if (traverseChildrenPred.apply(n)) {
2721  2496 for (Node c = n.getFirstChild(); c != null; c = c.getNext()) {
2722  1214 total += getCount(c, pred, traverseChildrenPred);
2723    }
2724    }
2725   
2726  1466 return total;
2727    }
2728   
2729    /**
2730    * Interface for use with the visit method.
2731    * @see #visit
2732    */
 
2733    static interface Visitor {
2734    void visit(Node node);
2735    }
2736   
2737    /**
2738    * A pre-order traversal, calling Visitor.visit for each child matching
2739    * the predicate.
2740    */
 
2741  397 toggle static void visitPreOrder(Node node,
2742    Visitor visitor,
2743    Predicate<Node> traverseChildrenPred) {
2744  397 visitor.visit(node);
2745   
2746  397 if (traverseChildrenPred.apply(node)) {
2747  685 for (Node c = node.getFirstChild(); c != null; c = c.getNext()) {
2748  292 visitPreOrder(c, visitor, traverseChildrenPred);
2749    }
2750    }
2751    }
2752   
2753    /**
2754    * A post-order traversal, calling Visitor.visit for each child matching
2755    * the predicate.
2756    */
 
2757  630 toggle static void visitPostOrder(Node node,
2758    Visitor visitor,
2759    Predicate<Node> traverseChildrenPred) {
2760  630 if (traverseChildrenPred.apply(node)) {
2761  1152 for (Node c = node.getFirstChild(); c != null; c = c.getNext()) {
2762  543 visitPostOrder(c, visitor, traverseChildrenPred);
2763    }
2764    }
2765   
2766  630 visitor.visit(node);
2767    }
2768   
2769    /**
2770    * @return Whether a TRY node has a finally block.
2771    */
 
2772  146 toggle static boolean hasFinally(Node n) {
2773  146 Preconditions.checkArgument(n.isTry());
2774  146 return n.getChildCount() == 3;
2775    }
2776   
2777    /**
2778    * @return The BLOCK node containing the CATCH node (if any)
2779    * of a TRY.
2780    */
 
2781  323 toggle static Node getCatchBlock(Node n) {
2782  323 Preconditions.checkArgument(n.isTry());
2783  323 return n.getFirstChild().getNext();
2784    }
2785   
2786    /**
2787    * @return Whether BLOCK (from a TRY node) contains a CATCH.
2788    * @see NodeUtil#getCatchBlock
2789    */
 
2790  140 toggle static boolean hasCatchHandler(Node n) {
2791  140 Preconditions.checkArgument(n.isBlock());
2792  140 return n.hasChildren() && n.getFirstChild().isCatch();
2793    }
2794   
2795    /**
2796    * @param fnNode The function.
2797    * @return The Node containing the Function parameters.
2798    */
 
2799  780 toggle public static Node getFunctionParameters(Node fnNode) {
2800    // Function NODE: [ FUNCTION -> NAME, LP -> ARG1, ARG2, ... ]
2801  780 Preconditions.checkArgument(fnNode.isFunction());
2802  780 return fnNode.getFirstChild().getNext();
2803    }
2804   
2805    /**
2806    * Returns true if a name node represents a constant variable.
2807    *
2808    * <p>Determining whether a variable is constant has three steps:
2809    * <ol>
2810    * <li>In CodingConventionAnnotator, any name that matches the
2811    * {@link CodingConvention#isConstant(String)} is annotated with an
2812    * IS_CONSTANT_NAME property.
2813    * <li>The normalize pass renames any variable with the IS_CONSTANT_NAME
2814    * annotation and that is initialized to a constant value with
2815    * a variable name including $$constant.
2816    * <li>Return true here if the variable includes $$constant in its name.
2817    * </ol>
2818    *
2819    * @param node A NAME or STRING node
2820    * @return True if the variable is constant
2821    */
 
2822  10955 toggle static boolean isConstantName(Node node) {
2823  10955 return node.getBooleanProp(Node.IS_CONSTANT_NAME);
2824    }
2825   
2826    /** Whether the given name is constant by coding convention. */
 
2827  93397 toggle static boolean isConstantByConvention(
2828    CodingConvention convention, Node node, Node parent) {
2829  93397 String name = node.getString();
2830  93397 if (parent.isGetProp() &&
2831    node == parent.getLastChild()) {
2832  16331 return convention.isConstantKey(name);
2833  77066 } else if (isObjectLitKey(node, parent)) {
2834  705 return convention.isConstantKey(name);
2835    } else {
2836  76361 return convention.isConstant(name);
2837    }
2838    }
2839   
2840    /**
2841    * Get the JSDocInfo for a function.
2842    */
 
2843  316 toggle public static JSDocInfo getFunctionJSDocInfo(Node n) {
2844  316 Preconditions.checkState(n.isFunction());
2845  316 JSDocInfo fnInfo = n.getJSDocInfo();
2846  316 if (fnInfo == null && NodeUtil.isFunctionExpression(n)) {
2847    // Look for the info on other nodes.
2848  130 Node parent = n.getParent();
2849  130 if (parent.isAssign()) {
2850    // on ASSIGNs
2851  87 fnInfo = parent.getJSDocInfo();
2852  43 } else if (parent.isName()) {
2853    // on var NAME = function() { ... };
2854  20 fnInfo = parent.getParent().getJSDocInfo();
2855    }
2856    }
2857  316 return fnInfo;
2858    }
2859   
2860    /**
2861    * @param n The node.
2862    * @return The source name property on the node or its ancestors.
2863    */
 
2864  10350 toggle public static String getSourceName(Node n) {
2865  10350 String sourceName = null;
2866  20710 while (sourceName == null && n != null) {
2867  10360 sourceName = n.getSourceFileName();
2868  10360 n = n.getParent();
2869    }
2870  10350 return sourceName;
2871    }
2872   
2873    /**
2874    * @param n The node.
2875    * @return The source name property on the node or its ancestors.
2876    */
 
2877  5 toggle public static StaticSourceFile getSourceFile(Node n) {
2878  5 StaticSourceFile sourceName = null;
2879  9 while (sourceName == null && n != null) {
2880  4 sourceName = n.getStaticSourceFile();
2881  4 n = n.getParent();
2882    }
2883  5 return sourceName;
2884    }
2885   
2886    /**
2887    * @param n The node.
2888    * @return The InputId property on the node or its ancestors.
2889    */
 
2890  121220 toggle public static InputId getInputId(Node n) {
2891  286356 while (n != null && !n.isScript()) {
2892  165136 n = n.getParent();
2893    }
2894   
2895  121220 return (n != null && n.isScript()) ? n.getInputId() : null;
2896    }
2897   
2898    /**
2899    * A new CALL node with the "FREE_CALL" set based on call target.
2900    */
 
2901  0 toggle static Node newCallNode(Node callTarget, Node... parameters) {
2902  0 boolean isFreeCall = !isGet(callTarget);
2903  0 Node call = IR.call(callTarget);
2904  0 call.putBooleanProp(Node.FREE_CALL, isFreeCall);
2905  0 for (Node parameter : parameters) {
2906  0 call.addChildToBack(parameter);
2907    }
2908  0 return call;
2909    }
2910   
2911    /**
2912    * @return Whether the node is known to be a value that is not referenced
2913    * elsewhere.
2914    */
 
2915  476 toggle static boolean evaluatesToLocalValue(Node value) {
2916  476 return evaluatesToLocalValue(value, Predicates.<Node>alwaysFalse());
2917    }
2918   
2919    /**
2920    * @param locals A predicate to apply to unknown local values.
2921    * @return Whether the node is known to be a value that is not a reference
2922    * outside the expression scope.
2923    */
 
2924  711 toggle static boolean evaluatesToLocalValue(Node value, Predicate<Node> locals) {
2925  711 switch (value.getType()) {
2926  0 case Token.CAST:
2927  0 return evaluatesToLocalValue(value.getFirstChild(), locals);
2928  12 case Token.ASSIGN:
2929    // A result that is aliased by a non-local name, is the effectively the
2930    // same as returning a non-local name, but this doesn't matter if the
2931    // value is immutable.
2932  12 return NodeUtil.isImmutableValue(value.getLastChild())
2933    || (locals.apply(value)
2934    && evaluatesToLocalValue(value.getLastChild(), locals));
2935  4 case Token.COMMA:
2936  4 return evaluatesToLocalValue(value.getLastChild(), locals);
2937  7 case Token.AND:
2938  12 case Token.OR:
2939  19 return evaluatesToLocalValue(value.getFirstChild(), locals)
2940    && evaluatesToLocalValue(value.getLastChild(), locals);
2941  16 case Token.HOOK:
2942  16 return evaluatesToLocalValue(value.getFirstChild().getNext(), locals)
2943    && evaluatesToLocalValue(value.getLastChild(), locals);
2944  2 case Token.INC:
2945  2 case Token.DEC:
2946  4 if (value.getBooleanProp(Node.INCRDECR_PROP)) {
2947  2 return evaluatesToLocalValue(value.getFirstChild(), locals);
2948    } else {
2949  2 return true;
2950    }
2951  58 case Token.THIS:
2952  58 return locals.apply(value);
2953  218 case Token.NAME:
2954  218 return isImmutableValue(value) || locals.apply(value);
2955  3 case Token.GETELEM:
2956  147 case Token.GETPROP:
2957    // There is no information about the locality of object properties.
2958  150 return locals.apply(value);
2959  20 case Token.CALL:
2960  20 return callHasLocalResult(value)
2961    || isToStringMethodCall(value)
2962    || locals.apply(value);
2963  30 case Token.NEW:
2964  30 return newHasLocalResult(value)
2965    || locals.apply(value);
2966  43 case Token.FUNCTION:
2967  0 case Token.REGEXP:
2968  7 case Token.ARRAYLIT:
2969  51 case Token.OBJECTLIT:
2970    // Literals objects with non-literal children are allowed.
2971  101 return true;
2972  1 case Token.DELPROP:
2973  1 case Token.IN:
2974    // TODO(johnlenz): should IN operator be included in #isSimpleOperator?
2975  2 return true;
2976  77 default:
2977    // Other op force a local value:
2978    // x = '' + g (x is now an local string)
2979    // x -= g (x is now an local number)
2980  77 if (isAssignmentOp(value)
2981    || isSimpleOperator(value)
2982    || isImmutableValue(value)) {
2983  77 return true;
2984    }
2985   
2986  0 throw new IllegalStateException(
2987    "Unexpected expression node" + value +
2988    "\n parent:" + value.getParent());
2989    }
2990    }
2991   
2992    /**
2993    * Given the first sibling, this returns the nth
2994    * sibling or null if no such sibling exists.
2995    * This is like "getChildAtIndex" but returns null for non-existent indexes.
2996    */
 
2997  290 toggle private static Node getNthSibling(Node first, int index) {
2998  290 Node sibling = first;
2999  442 while (index != 0 && sibling != null) {
3000  152 sibling = sibling.getNext();
3001  152 index--;
3002    }
3003  290 return sibling;
3004    }
3005   
3006    /**
3007    * Given the function, this returns the nth
3008    * argument or null if no such parameter exists.
3009    */
 
3010  41 toggle static Node getArgumentForFunction(Node function, int index) {
3011  41 Preconditions.checkState(function.isFunction());
3012  41 return getNthSibling(
3013    function.getFirstChild().getNext().getFirstChild(), index);
3014    }
3015   
3016    /**
3017    * Given the new or call, this returns the nth
3018    * argument of the call or null if no such argument exists.
3019    */
 
3020  249 toggle static Node getArgumentForCallOrNew(Node call, int index) {
3021  249 Preconditions.checkState(isCallOrNew(call));
3022  249 return getNthSibling(
3023    call.getFirstChild().getNext(), index);
3024    }
3025   
3026    /**
3027    * Returns whether this is a target of a call or new.
3028    */
 
3029  9630 toggle static boolean isCallOrNewTarget(Node target) {
3030  9630 Node parent = target.getParent();
3031  9630 return parent != null
3032    && NodeUtil.isCallOrNew(parent)
3033    && parent.getFirstChild() == target;
3034    }
3035   
 
3036  16 toggle private static boolean isToStringMethodCall(Node call) {
3037  16 Node getNode = call.getFirstChild();
3038  16 if (isGet(getNode)) {
3039  10 Node propNode = getNode.getLastChild();
3040  10 return propNode.isString() && "toString".equals(propNode.getString());
3041    }
3042  6 return false;
3043    }
3044   
3045    /** Find the best JSDoc for the given node. */
 
3046  44013 toggle static JSDocInfo getBestJSDocInfo(Node n) {
3047  44013 JSDocInfo info = n.getJSDocInfo();
3048  44013 if (info == null) {
3049  40626 Node parent = n.getParent();
3050  40626 if (parent == null) {
3051  0 return null;
3052    }
3053   
3054  40626 if (parent.isName()) {
3055  332 return getBestJSDocInfo(parent);
3056  40294 } else if (parent.isAssign()) {
3057  1507 return parent.getJSDocInfo();
3058  38787 } else if (isObjectLitKey(parent, parent.getParent())) {
3059  83 return parent.getJSDocInfo();
3060  38704 } else if (parent.isFunction()) {
3061  10389 return parent.getJSDocInfo();
3062  28315 } else if (parent.isVar() && parent.hasOneChild()) {
3063  20148 return parent.getJSDocInfo();
3064  8167 } else if ((parent.isHook() && parent.getFirstChild() != n) ||
3065    parent.isOr() ||
3066    parent.isAnd() ||
3067    (parent.isComma() && parent.getFirstChild() != n)) {
3068  14 return getBestJSDocInfo(parent);
3069  8153 } else if (parent.isCast()) {
3070  2 return parent.getJSDocInfo();
3071    }
3072    }
3073  11538 return info;
3074    }
3075   
3076    /** Find the l-value that the given r-value is being assigned to. */
 
3077  6986 toggle static Node getBestLValue(Node n) {
3078  6986 Node parent = n.getParent();
3079  6986 boolean isFunctionDeclaration = isFunctionDeclaration(n);
3080  6986 if (isFunctionDeclaration) {
3081  3336 return n.getFirstChild();
3082  3650 } else if (parent.isName()) {
3083  790 return parent;
3084  2860 } else if (parent.isAssign()) {
3085  2400 return parent.getFirstChild();
3086  460 } else if (isObjectLitKey(parent, parent.getParent())) {
3087  285 return parent;
3088  175 } else if (
3089  175 (parent.isHook() && parent.getFirstChild() != n) ||
3090    parent.isOr() ||
3091    parent.isAnd() ||
3092    (parent.isComma() && parent.getFirstChild() != n)) {
3093  26 return getBestLValue(parent);
3094  149 } else if (parent.isCast()) {
3095  2 return getBestLValue(parent);
3096    }
3097  147 return null;
3098    }
3099   
3100    /** Gets the r-value of a node returned by getBestLValue. */
 
3101  8319 toggle static Node getRValueOfLValue(Node n) {
3102  8319 Node parent = n.getParent();
3103  8319 switch (parent.getType()) {
3104  357 case Token.ASSIGN:
3105  357 return n.getNext();
3106  1078 case Token.VAR:
3107  1078 return n.getFirstChild();
3108  6831 case Token.FUNCTION:
3109  6831 return parent;
3110    }
3111  53 return null;
3112    }
3113   
3114    /** Get the owner of the given l-value node. */
 
3115  4539 toggle static Node getBestLValueOwner(@Nullable Node lValue) {
3116  4539 if (lValue == null || lValue.getParent() == null) {
3117  72 return null;
3118    }
3119  4467 if (isObjectLitKey(lValue, lValue.getParent())) {
3120  24 return getBestLValue(lValue.getParent());
3121  4443 } else if (isGet(lValue)) {
3122  1198 return lValue.getFirstChild();
3123    }
3124   
3125  3245 return null;
3126    }
3127   
3128    /** Get the name of the given l-value node. */
 
3129  10995 toggle static String getBestLValueName(@Nullable Node lValue) {
3130  10995 if (lValue == null || lValue.getParent() == null) {
3131  3431 return null;
3132    }
3133  7564 if (isObjectLitKey(lValue, lValue.getParent())) {
3134  427 Node owner = getBestLValue(lValue.getParent());
3135  427 if (owner != null) {
3136  413 String ownerName = getBestLValueName(owner);
3137  413 if (ownerName != null) {
3138  412 return ownerName + "." + getObjectLitKeyName(lValue);
3139    }
3140    }
3141  15 return null;
3142    }
3143  7137 return lValue.getQualifiedName();
3144    }
3145   
3146    /**
3147    * @returns false iff the result of the expression is not consumed.
3148    */
 
3149  4558 toggle static boolean isExpressionResultUsed(Node expr) {
3150    // TODO(johnlenz): consider sharing some code with trySimpleUnusedResult.
3151  4558 Node parent = expr.getParent();
3152  4558 switch (parent.getType()) {
3153  387 case Token.BLOCK:
3154  544 case Token.EXPR_RESULT:
3155  931 return false;
3156  3 case Token.CAST:
3157  3 return isExpressionResultUsed(parent);
3158  6 case Token.HOOK:
3159  4 case Token.AND:
3160  8 case Token.OR:
3161  18 return (expr == parent.getFirstChild())
3162    ? true : isExpressionResultUsed(parent);
3163  8 case Token.COMMA:
3164  8 Node gramps = parent.getParent();
3165  4 if (gramps.isCall() &&
3166    parent == gramps.getFirstChild()) {
3167    // Semantically, a direct call to eval is different from an indirect
3168    // call to an eval. See ECMA-262 S15.1.2.1. So it's OK for the first
3169    // expression to a comma to be a no-op if it's used to indirect
3170    // an eval. This we pretend that this is "used".
3171  0 if (expr == parent.getFirstChild() &&
3172    parent.getChildCount() == 2 &&
3173    expr.getNext().isName() &&
3174    "eval".equals(expr.getNext().getString())) {
3175  0 return true;
3176    }
3177    }
3178   
3179  7 return (expr == parent.getFirstChild())
3180    ? false : isExpressionResultUsed(parent);
3181  16 case Token.FOR:
3182  16 if (!NodeUtil.isForIn(parent)) {
3183    // Only an expression whose result is in the condition part of the
3184    // expression is used.
3185  14 return (parent.getChildAtIndex(1) == expr);
3186    }
3187  2 break;
3188    }
3189  3584 return true;
3190    }
3191   
3192    /**
3193    * @param n The expression to check.
3194    * @return Whether the expression is unconditionally executed only once in the
3195    * containing execution scope.
3196    */
 
3197  49 toggle static boolean isExecutedExactlyOnce(Node n) {
3198  49 inspect: do {
3199  132 Node parent = n.getParent();
3200  132 switch (parent.getType()) {
3201  10 case Token.IF:
3202  4 case Token.HOOK:
3203  6 case Token.AND:
3204  3 case Token.OR:
3205  23 if (parent.getFirstChild() != n) {
3206  15 return false;
3207    }
3208    // other ancestors may be conditional
3209  8 continue inspect;
3210  9 case Token.FOR:
3211  9 if (NodeUtil.isForIn(parent)) {
3212  4 if (parent.getChildAtIndex(1) != n) {
3213  3 return false;
3214    }
3215    } else {
3216  5 if (parent.getFirstChild() != n) {
3217  3 return false;
3218    }
3219    }
3220    // other ancestors may be conditional
3221  3 continue inspect;
3222  2 case Token.WHILE:
3223  2 case Token.DO:
3224  4 return false;
3225  4 case Token.TRY:
3226    // Consider all code under a try/catch to be conditionally executed.
3227  4 if (!hasFinally(parent) || parent.getLastChild() != n) {
3228  2 return false;
3229    }
3230  2 continue inspect;
3231  2 case Token.CASE:
3232  1 case Token.DEFAULT_CASE:
3233  3 return false;
3234  11 case Token.SCRIPT:
3235  8 case Token.FUNCTION:
3236    // Done, we've reached the scope root.
3237  19 break inspect;
3238    }
3239  ? } while ((n = n.getParent()) != null);
3240  19 return true;
3241    }
3242   
3243    /**
3244    * @return An appropriate AST node for the boolean value.
3245    */
 
3246  4081 toggle static Node booleanNode(boolean value) {
3247  4081 return value ? IR.trueNode() : IR.falseNode();
3248    }
3249   
3250    /**
3251    * @return An appropriate AST node for the double value.
3252    */
 
3253  5529 toggle static Node numberNode(double value, Node srcref) {
3254  5529 Node result;
3255  5529 if (Double.isNaN(value)) {
3256  1410 result = IR.name("NaN");
3257  4119 } else if (value == Double.POSITIVE_INFINITY) {
3258  27 result = IR.name("Infinity");
3259  4092 } else if (value == Double.NEGATIVE_INFINITY) {
3260  296 result = IR.neg(IR.name("Infinity"));
3261    } else {
3262  3796 result = IR.number(value);
3263    }
3264  5529 if (srcref != null) {
3265  3280 result.srcrefTree(srcref);
3266    }
3267  5529 return result;
3268    }
3269   
 
3270  39 toggle static boolean isNaN(Node n) {
3271  39 if ((n.isName() && n.getString().equals("NaN")) ||
3272    (n.getType() == Token.DIV &&
3273    n.getFirstChild().isNumber() && n.getFirstChild().getDouble() == 0 &&
3274    n.getLastChild().isNumber() && n.getLastChild().getDouble() == 0)) {
3275  18 return true;
3276    }
3277  21 return false;
3278    }
3279    }